LeetCode 筆記 - 256. Paint House

解析 LeetCode 經典題「粉刷房子」。本文探討如何在顏色不相鄰的限制下，運用動態規劃（DP）找出粉刷所有房子的最低成本。透過建立狀態轉移方程，逐層累加當前顏色的最優解，是理解 DP 處理相鄰約束問題的入門首選。

發佈

2022.08.03

閱讀

約 1 分鐘

字數

205

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 256. Paint House

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

解題思維

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

程式碼

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])

解題思維

程式碼

也許你也會想看看