剑指 Offer II 091. 粉刷房子

原题链接：剑指 Offer II 091. 粉刷房子

solution:

        简单dp

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int> (3));
        //dp[i][j]表示把前i个房子染色,第i个房子染成j颜色的最小花费
        //0:红色 1:蓝色 2:绿色
        dp[1][0] = costs[0][0];
        dp[1][1] = costs[0][1];
        dp[1][2] = costs[0][2];

        for(int i = 2;i <= n;i++) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }

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