---
title: "256. Paint House"
url: "https://laigary.com/interview/coding/256-paint-house"
type: "note"
section: "coding"
date: "2026-01-03"
updated: "2026-07-29"
tags: ["Dynamic Programming"]
---

# 256. Paint House

[256\. Paint House](https://leetcode.com/problems/paint-house/)

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

## 思路

這題和 [198. House Robber](/interview/coding/198-house-robber) 是同一個家族：**一排東西、相鄰有限制、求最佳解**。差別在於限制的形式：

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

所以狀態是二維的：

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

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

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

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

## 解題方向

```python
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`。

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

```python
        @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](/interview/coding/265-paint-house-ii)（`k` 種顏色）的情況。

### 自底向上

```python
        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](/interview/coding/265-paint-house-ii) 是 `k` 種顏色的版本。** 直接套上面的做法會變成 $O(nk^2)$（每間房子對每種顏色都要掃一遍其他顏色找最小）。那題的重點是把它優化到 $O(nk)$ —— 訣竅是**只記住前一列的最小值和次小值**：如果當前顏色不等於「最小值的那個顏色」，就用最小值；等於的話就用次小值。這是這一系列裡真正的考點。

**和 [198. House Robber](/interview/coding/198-house-robber) 的對照**值得記住：

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

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

**同一個「一排 + 相鄰限制」家族**：[198. House Robber](/interview/coding/198-house-robber)、[213. House Robber II](/interview/coding/213-house-robber-ii)、[276. Paint Fence](/interview/coding/276-paint-fence)。整理見 [Dynamic Programming 模板](/interview/coding/dynamic-programming-template)。

## 複雜度

**自頂向下（記憶化）**
- 時間 $O(n)$ — 狀態數是 `n × 4`（位置 × 上一間的顏色），每個狀態常數時間；嚴格寫是 $O(nk^2)$，這裡 `k=3` 是常數
- 空間 $O(n)$ — cache 加上遞迴堆疊

**自底向上（滾動）**
- 時間 $O(n)$
- 空間 $O(1)$ — 只有一個長度 3 的陣列

其中 `n` 是房子數。顏色數固定為 3 所以被吸收成常數；換成 [265](/interview/coding/265-paint-house-ii) 的 `k` 色就要寫成 $O(nk)$。