LeetCode 筆記 - 256. Paint House

Posted on

題目在此 256. Paint House

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

解題思維

各位同學，就是 Dynamic programming
對，就是它

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        # red, blue, or green
        
        if (size := len(costs)) == 1:
            return min(costs[0])
        
        for i in range(1, size):
            costs[i][0] += min(costs[i - 1][1], costs[i - 1][2])
            costs[i][1] += min(costs[i - 1][0], costs[i - 1][2])
            costs[i][2] += min(costs[i - 1][0], costs[i - 1][1])
            
        return min(costs[-1])

相關文章