有
n棟房子排成一列，每棟可以漆成紅、藍、綠三色之一，相鄰房子不能同色。costs[i][j]是第i棟漆成第j種顏色的成本。求漆完所有房子的最小總成本。
Example:
Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10
Intuition
TIP
每棟房子選一個顏色，且不能和前一棟相同 — 對每個顏色追蹤到此為止的最小成本。
dp[i][c]= 把前i棟房子漆完，第i棟漆顏色c的最小成本- 狀態轉移：
dp[i][c] = costs[i][c] + min(dp[i-1][其他兩色]) - 只依賴前一行，可以用三個變數滾動
Approaches
1. Bottom-Up DP — O(n) / O(n)
- Idea: 二維 DP 表，逐行填入每種顏色的最小累計成本
- Time:
O(n) - Space:
O(n)
class Solution {
fun minCost(costs: Array<IntArray>): Int {
val n = costs.size
val dp = Array(n) { IntArray(3) }
dp[0] = costs[0].copyOf()
for (i in 1 until n) {
dp[i][0] = costs[i][0] + minOf(dp[i - 1][1], dp[i - 1][2])
dp[i][1] = costs[i][1] + minOf(dp[i - 1][0], dp[i - 1][2])
dp[i][2] = costs[i][2] + minOf(dp[i - 1][0], dp[i - 1][1])
}
return dp[n - 1].min()
}
}⭐ 2. Rolling Variables — O(n) / O(1)
- Idea: 只保留前一棟房子的三個顏色成本，空間最優
- Time:
O(n) - Space:
O(1)
class Solution {
fun minCost(costs: Array<IntArray>): Int {
var r = costs[0][0]
var b = costs[0][1]
var g = costs[0][2]
for (i in 1 until costs.size) {
val nr = costs[i][0] + minOf(b, g)
val nb = costs[i][1] + minOf(r, g)
val ng = costs[i][2] + minOf(r, b)
r = nr; b = nb; g = ng
}
return minOf(r, b, g)
}
}🔑 Takeaways
- Pattern: 多選項線性 DP — 每一步有固定數量的選擇，且有約束條件
- Key trick: 顏色數量固定（3 種），所以「取其他選項的最小值」可以直接寫出來，不需要額外迴圈