用取捨DP框架來上色 粉刷房屋I_Paint House_Leetcode #256

Greg Rivers on Unsplash

題目敘述 Paint House

題目會給定一個成本陣列costs，分別代表每棟房屋粉刷成紅色、藍色、綠色的成本。

請問粉刷所有房屋的最小成本是多少，而且相鄰的房屋不可同一種顏色。

註: 如果您是沒有訂閱Leetcode Premium的讀者，
可以到這邊看原文題目和上機考平臺練習。

測試範例

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

第一棟房屋著成藍色，花費2元。
第二棟房屋著成​綠色，花費5元。
第三棟房屋著成藍色，花費3元。
總共花費2+5+3元。​

Example 2:

Input: costs = [[7,6,2]]
Output: 2

第一棟房屋著成綠色，花費2元。
總共花費2+5+3元。​

約束條件

Constraints:

• costs.length == n

輸入陣列總長度為n，代表有n棟房屋。

• costs[i].length == 3

cost[i]代表第i棟房屋著成成紅色、藍色、綠色的成本。

• 1 <= n <= 100

房屋總數n值 介於 1~100

• 1 <= costs[i][j] <= 20

單次著色成本介於1~20之間。

觀察 同色不相鄰

題目的意思換句話說就是同色不相鄰之下的全體著色最小成本。

現在當下在第i棟房屋，每個顏色都有取/不取兩種可能，
取了這個顏色，下一棟就不可以用這個顏色。

我們可以定義DP[i, prevColor]代表第i棟房屋~最後一棟房屋的最小著色成本，prevColor代表前一棟被用掉的顏色。

DP[i, prevColor]代表第i棟房屋~最後一棟房屋的最小著色成本

= min{ 第i棟房屋房屋選一個不和前一棟重複的顏色著色，接著考慮下一棟 }

= min{ costs[i][color] + DP[i+1, color] where color != prevColor }

什麼時候停下來?

當已經塗完最後一棟房屋的時候，這時候已經沒有更多房子了，成本=0

DP[i, prevColor] = 0, if i = n = 房屋總數 = len( costs )

演算法 DP動態規劃 + 取捨DP框架

1.定義DP狀態

承接觀察點的思考

我們可以定義DP[i, prevColor]代表第i棟房屋~最後一棟房屋的最小著色成本，prevColor代表前一棟被用掉的顏色。

最終目標是什麼?

目標是所有房屋 第一棟~最後一棟的整體著色最小成本

= DP[ 0, prevColor = DUMMY 第一棟沒有前一棟，所以顏色可以任選 ]

2.推導DP狀態轉移關係式

現在要做的是計算同色不相鄰之下的全體著色最小成本。

現在當下在第i棟房屋，每個顏色都有取/不取兩種可能，

取了這個顏色，下一棟就不可以用這個顏色。

DP[i, prevColor]代表第i棟房屋~最後一棟房屋的最小著色成本

= min{ 第i棟房屋房屋選一個不和前一棟重複的顏色著色，接著考慮下一棟 }

= min{ costs[i][color] + DP[i+1, color] where color != prevColor }

3.釐清DP初始狀態

什麼時候停下來?

最小規模的問題是什麼?

當已經塗完最後一棟房屋的時候，這時候已經沒有更多房子了，成本=0

DP[i, prevColor] = 0, if i = n = 房屋總數 = len( costs )

程式碼 DP動態規劃 + 取捨DP框架

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        
        # COLOR Constant to helper reader understand source code
        DUMMY, RED, BLUE, GREEN = -1, 0, 1, 2

        # DP table
        dp = {}

        # Paint house i to last house with overall minimal cost
        def paint( i, prevColor ):
            
            ## Base case:
            # No more house, cost = 0
            if i == (len(costs)):
                dp[i, prevColor] = 0 
                return 0

            ## Look-up DP table
            if (i, prevColor) in dp:
                return dp[(i, prevColor)]

            ## General cases
            # Paint current house with different color to previous house.
            # Choose minimal overall cost
            minCost = min( [costs[i][color] + paint(i+1, prevColor=color) for color in range(3) if color != prevColor] )
            dp[(i, prevColor)] = minCost
            return minCost

        # -------------------------------

        return paint(i=0, prevColor=DUMMY)
                

複雜度分析

時間複雜度:O(n)

線性掃描每棟房屋，每棟房屋可以在O(1)選擇最佳的著色方案。

空間複雜度: O(n)

DP table 所需空間大小為O(3n)，紀錄每棟房屋~最後一棟房屋對應的最小著色成本。

關鍵知識點

這題的限制在於同色不相鄰。

每個顏色 只有選 或是 不選 兩種可能，
一旦選擇了，下一棟房屋就不可以重複用同樣的顏色。

對應到的就是 取(著這個顏色)/不取(不著這格顏色) 的DP框架，

比較接近的是House Robbery的系列題(每棟房屋要嘛選擇，要嘛跳過)，

強烈建議讀者一起複習，鞏固知識點。

一魚多吃 用DP解House Robbery 打家劫舍問題_Leetcode #198_Leetcode 精選75題解析

化簡無所不在 用學過的DP模型解House Robbery II_Leetcode #213

合縱連橫: 從區間DP理解House Robbery系列題 背後的本質

類似的還有用取捨DP來考高分 Solving Questions With Brainpower

Reference

[1] Paint House - LeetCode

回到DP特訓班目錄 和 學習路徑