Simple Java DP solution


  • 1
    M
    public class Solution {
        public int minCost(int[][] costs) {
            if(costs==null || costs.length==0)
            return 0;
            
        int[][] housecost=new int[costs.length+1][3];
        housecost[0][0]=0;housecost[0][1]=0;housecost[0][2]=0;
        for(int i=1;i<=costs.length;i++){
            housecost[i][0]=Math.min(housecost[i-1][1]+costs[i-1][0],housecost[i-1][2]+costs[i-1][0]);
            housecost[i][1]=Math.min(housecost[i-1][0]+costs[i-1][1],housecost[i-1][2]+costs[i-1][1]);
            housecost[i][2]=Math.min(housecost[i-1][0]+costs[i-1][2],housecost[i-1][1]+costs[i-1][2]);
            
            
            
        }
        return Math.min(Math.min(housecost[costs.length][0],housecost[costs.length][1]),housecost[costs.length][2]);
            
        }
    }

  • 0
    X

    //Solution for Paint House II

    public class Solution {

    public int minCostII(int[][] costs) {
        if(costs == null || costs.length < 1)return 0;
        int k = costs[0].length;
        if(k == 1){
            int ret = 0;
            for(int i = 0; i < costs.length; i++)ret += costs[i][0];
            return ret;
        }
    
        int[][] houseCost = new int[costs.length+1][k];
        for(int i = 0; i < k; i++){
            houseCost[0][i] = 0;
        }
        
        for(int i = 1; i <= costs.length; i++){
            for(int j = 0; j < k; j++){
                 houseCost[i][j] = Integer.MAX_VALUE;
                 for(int n = 0; n < k; n++){
                     if(n != j){
                        houseCost[i][j] = Math.min(houseCost[i][j], houseCost[i - 1][n] + costs[i - 1][j]);
                        
                     }
                 }
            }
        }
        
        int min = Integer.MAX_VALUE;
        for(int j = 0; j < k; j++){
            min = Math.min(houseCost[costs.length][j], min);
        }
        return min;
    }
    

    }


Log in to reply
 

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