Easy Java DP with %


  • 0
    M
    public class Solution {
        public int minCost(int[][] costs) {
            if (costs.length == 0) return 0;
            int[][] dp = new int[costs.length][costs[0].length];
            for (int i = 0; i < 3; i++) dp[0][i] = costs[0][i];
            for (int i = 1;i<costs.length;i++) {
            //make j from 3 to 5,once a house is painted with color j%3, its last valid color is (j-1)%3 and (j+1)%3. 
                for (int j = 3;j<6;j++)
                    dp[i][j%3] =costs[i][j%3]+ Math.min(dp[i-1][(j-1)%3],dp[i-1][(j+1)%3]);
            }
            int min = Integer.MAX_VALUE;
            for (int m : dp[costs.length - 1]) {
                min = Math.min(min, m);
            }
            return min;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.