256. Paint House

──────────────────────────────────────────────────────────────────────

256. Paint House

一排房子要漆成紅、藍、綠三色之一，每間房子漆每種顏色的成本不同，相鄰兩間不能同色。求最小總成本。

思路

這題和 198. House Robber 是同一個家族：一排東西、相鄰有限制、求最佳解。差別在於限制的形式：

198 的限制是「相鄰不能都選」→ 狀態只要記位置
這題的限制是「相鄰不能同色」→ 狀態要記位置和顏色

所以狀態是二維的：

dp(i, prev) = 從第 i 間房子開始往後、且第 i-1 間漆了 prev 色，最少還要花多少

多出來的那個 prev 就是「限制需要多少資訊才能表達」的答案。這是 DP 題最常見的加維理由 —— 限制看得到多遠，狀態就要記多少。

base case 是 i == n（沒有房子了，花費 0）。

第一間房子沒有「前一間」怎麼辦？ 用一個不會等於 0/1/2 的哨兵值當初始的 prev，讓它落進「三種顏色都可以選」的分支。

解題方向

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        if not costs:
            return 0
        n = len(costs)

        @cache
        def helper(i, prev):
            if i == n:
                return 0
            if prev == 0:
                return min(
                    costs[i][1] + helper(i + 1, 1),
                    costs[i][2] + helper(i + 1, 2),
                )
            elif prev == 1:
                return min(
                    costs[i][0] + helper(i + 1, 0),
                    costs[i][2] + helper(i + 1, 2),
                )
            elif prev == 2:
                return min(
                    costs[i][0] + helper(i + 1, 0),
                    costs[i][1] + helper(i + 1, 1),
                )
            else:
                return min(
                    costs[i][0] + helper(i + 1, 0),
                    costs[i][1] + helper(i + 1, 1),
                    costs[i][2] + helper(i + 1, 2)
                )
        
        return helper(0, float('inf'))

四個分支分別是「上一間是紅 / 藍 / 綠 / 還沒有上一間」，每個分支只考慮和 prev 不同的顏色。helper(0, float('inf')) 用 inf 當哨兵落進最後那個 else。

這四個分支可以壓成一個迴圈，寫起來短很多也比較好擴充：

        @cache
        def helper(i, prev):
            if i == n:
                return 0
            return min(costs[i][c] + helper(i + 1, c)
                       for c in range(3) if c != prev)

prev 初始給 -1（或任何不在 0..2 的值），c != prev 就自動涵蓋了「第一間可以選任何顏色」。顏色數變多時這版不用改，而展開成 if/elif 的版本要重寫 —— 這正是 265. Paint House II（k 種顏色）的情況。

自底向上

        prev = list(costs[0])
        for i in range(1, n):
            prev = [costs[i][c] + min(prev[j] for j in range(3) if j != c)
                    for c in range(3)]
        return min(prev)

prev[c] 是「第 i 間漆成 c 色時，前 i+1 間的最小總成本」。只依賴前一列，所以用一個長度 3 的陣列滾動就好，空間 $O (1)$ 。

補充

265. Paint House II 是 k 種顏色的版本。 直接套上面的做法會變成 $O (n k^{2})$ （每間房子對每種顏色都要掃一遍其他顏色找最小）。那題的重點是把它優化到 $O (n k)$ —— 訣竅是只記住前一列的最小值和次小值：如果當前顏色不等於「最小值的那個顏色」，就用最小值；等於的話就用次小值。這是這一系列裡真正的考點。

和 198. House Robber 的對照值得記住：

	限制	狀態
198 House Robber	相鄰不能都選	`dp[i]`（一維）
256 這題	相鄰不能同色	`dp[i][color]`（二維）

「限制需要多少資訊，狀態就加多少維」 —— 這句話幾乎能解釋所有 DP 題的狀態設計。

同一個「一排 + 相鄰限制」家族：198. House Robber、213. House Robber II、276. Paint Fence。整理見 Dynamic Programming 模板。

複雜度

自頂向下（記憶化）

時間 $O (n)$ — 狀態數是 n × 4（位置 × 上一間的顏色），每個狀態常數時間；嚴格寫是 $O (n k^{2})$ ，這裡 k=3 是常數
空間 $O (n)$ — cache 加上遞迴堆疊

自底向上（滾動）

時間 $O (n)$
空間 $O (1)$ — 只有一個長度 3 的陣列

其中 n 是房子數。顏色數固定為 3 所以被吸收成常數；換成 265 的 k 色就要寫成 $O (n k)$ 。