題目會給定一個成本陣列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[i, prevColor]代表第i棟房屋~最後一棟房屋的最小著色成本,prevColor代表前一棟被用掉的顏色。
最終目標是什麼?
目標是所有房屋 第一棟~最後一棟的整體著色最小成本
= DP[ 0, prevColor = DUMMY 第一棟沒有前一棟,所以顏色可以任選 ]
現在要做的是計算同色不相鄰之下的全體著色最小成本。
現在當下在第i棟房屋,每個顏色都有取/不取兩種可能,
取了這個顏色,下一棟就不可以用這個顏色。
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 )
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(1)選擇最佳的著色方案。
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