Sword finger offer II 091 Paint the house

The finger of the sword Offer II 091. Paint the house

 

【DP】 Open one dp[n+1][3] Array of , For the first i The second house j Medium color , There can be a second i-1 The minimum value of two colors outside two houses .

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;
    }
}