# 256 - Paint House

解法一 - DP

這題要直接想出 DP 解並不是很容易，我們可以先從暴力解開始。暴力法基本上就是，遇到每一間 house，三種顏色都塗塗看，然後繼續往後 recursively 搜尋，看看這一間塗哪個顏色最好。

寫出來就是：

第一間塗紅，calculateMinCost(下一間不能是紅)
第一間塗藍，calculateMinCost(下一間不能是藍)
第一間塗綠，calculateMinCost(下一間不能是綠)

寫出上面這個暴力解法，就會發現我們在搜尋時，必須考慮上一間房子的顏色，才符合題目要求。所以這啟發了我們在寫 bottom-up DP 解的時候，每一間房子可能要有 3 種 min cost - 分別是這間房子塗紅、塗藍、塗綠的 min cost，而如果要塗紅，那上一間房子就必須是藍或綠，依照這個邏輯，我們可以寫出下面的程式碼：

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if(n <= 0) return 0;

        // dp[i][c] = the min cost when painting color c at i-th house
        vector<vector<int>> dp(n, vector<int>(3, 0));

        // Init
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];

        for(int h=1; h<n; h++) {
            int lastR = dp[h-1][0];
            int lastB = dp[h-1][1];
            int lastG = dp[h-1][2];

            dp[h][0] = min(lastB, lastG) + costs[h][0]; // Paint R on this house
            dp[h][1] = min(lastR, lastG) + costs[h][1]; // Paint B on this house
            dp[h][2] = min(lastR, lastB) + costs[h][2]; // Paint G on this house
        }

        return min(min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
    }
};