LeetCode 筆記 - 265. Paint House II

Posted on

題目在此 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])

相關文章