解題說明
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 狀態定義差異在哪?