剑指 Offer II 091. 粉刷房子

剑指 Offer II 091. 粉刷房子

 

【DP】开一个dp[n+1][3]的数组，对于第i个房子的第j中颜色，可以有第i-1个房子的两外两种颜色的最小值得到。

class Solution {

    //dp 1:21

    public int minCost(int[][] costs) {
        int n = costs.length;
        int max = 1 << 30, ans = max;
        int[][] dp = new int[n + 1][3];
        for(var i = 1; i <= n; i++){
            for(var j = 0; j < 3; j++){
                int min = max;
                for(var k = 0; k < 3; k++){
                    if(k == j) continue;
                    else min = Math.min(min, dp[i - 1][k]);
                }
                dp[i][j] = min + costs[i - 1][j];
                if(i == n){
                    ans = Math.min(dp[i][j], ans);
                }
            }
        }
        return ans;
    }
}