解題說明
Paint House
題目描述：
有一排 n 棟房子，每棟可以塗成紅、藍、綠三種顏色之一。塗不同顏色的成本不同，以 n×3 的矩陣 costs 表示，其中 costs[i][j] 代表第 i 棟房子塗第 j 種顏色的花費。要求相鄰的房子不能塗同一種顏色，求塗完所有房子的最小總花費。
解題思路：
典型的動態規劃問題。定義 dp[i][j] 為塗完前 i+1 棟房子、且第 i 棟塗第 j 種顏色的最小花費。
轉移方程：
dp[i][j] = costs[i][j] + min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3])
即第 i 棟塗顏色 j 的花費，加上前一棟塗另外兩種顏色的最小花費。
可以直接在 costs 陣列上原地修改，省去額外空間。最終答案為 min(dp[n-1][0], dp[n-1][1], dp[n-1][2])。
C++ 解法
複雜度分析
時間複雜度：O(n) — 遍歷所有房子一次，每棟房子做常數次運算（3 種顏色）。
空間複雜度：O(1) — 原地修改 costs 陣列，不需要額外空間。若不能修改輸入，可用三個變數滾動更新，仍為 O(1)。
虛擬碼
1. If costs is empty, return 0 2. For each house i from 1 to n-1: a. costs[i][0] += min(costs[i-1][1], costs[i-1][2]) b. costs[i][1] += min(costs[i-1][0], costs[i-1][2]) c. costs[i][2] += min(costs[i-1][0], costs[i-1][1]) 3. Return min(costs[n-1][0], costs[n-1][1], costs[n-1][2])
其他解法
記憶化搜尋 O(n)：自頂向下遞迴 + memo，dfs(i, color) 回傳從第 i 棟開始、第 i 棟塗 color 的最小花費。邏輯等價於 DP，但遞迴呼叫有額外開銷。
滾動變數優化：用三個變數 prev0, prev1, prev2 取代整個 DP 陣列。避免修改原始輸入，空間仍為 O(1)。適合面試中展示對空間優化的理解。
延伸思考
- 如果顏色從 3 種擴展到 k 種（LeetCode 265 Paint House II），如何將時間複雜度從 O(nk²) 優化到 O(nk)？（提示：記錄前一列的最小值和次小值）
- 如果允許最多 m 棟相鄰房子塗同一顏色（而非完全不能相鄰），轉移方程如何修改？
- 此題的結構與「打家劫舍」問題有何相似之處？兩者的 DP 狀態定義差異在哪？