256. Paint House

Medium

Description

有 n 棟房子排成一列，每棟可以漆成紅、藍、綠三色之一，相鄰房子不能同色。costs[i][j] 是第 i 棟漆成第 j 種顏色的成本。求漆完所有房子的最小總成本。

Example:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10

Intuition#

每棟房子選一個顏色，且不能和前一棟相同 — 對每個顏色追蹤到此為止的最小成本。

dp[i][c] = 把前 i 棟房子漆完，第 i 棟漆顏色 c 的最小成本
狀態轉移：dp[i][c] = costs[i][c] + min(dp[i-1][其他兩色])
只依賴前一行，可以用三個變數滾動

Approaches#

1: Bottom-Up DP#

概念: 二維 DP 表，逐行填入每種顏色的最小累計成本
時間複雜度: O(n)
空間複雜度: 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)

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 — 每一步有固定數量的選擇，且有約束條件
關鍵技巧: 顏色數量固定（3 種），所以「取其他選項的最小值」可以直接寫出來，不需要額外迴圈