LeetCode 筆記 - 265. Paint House II

Posted on 標籤
延續粉刷房子的概念，本題將顏色種類擴展至 k 種。解題思維同樣基於動態規劃，但需要處理更廣泛的顏色選擇範圍。本文解析如何在增加顏色靈活度的同時，依然保持演算法的執行效率，是進階動態規劃應用的優質練習。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 265. Paint House II

給定一系列，每個房子要漆成 k 種顏色的成本，但每種顏色不能相鄰
請問把所有房子漆完的最低成本？

解題思維

如果沒寫過第一題，可以先去看一下
LeetCode 筆記 - 256. Paint House

這題跟第一題不一樣的地方是，從固定三種顏色變成 ｋ 種
做法其實差不多，就是變成要掃過 k 種顏色

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        # red, blue, or green
        
        if (size := len(costs)) == 1:
            return min(costs[0])
        
        color_size = len(costs[0])
        
        for i in range(1, size):
            for c in range(color_size):
                min_value = inf
                for cc in range(color_size):
                    if cc == c:
                        continue
                    min_value = min(min_value, costs[i - 1][cc])
                    
                costs[i][c] += min_value
            
        return min(costs[-1])

也許你也會想看看