Dynamic Programming


  • 0
    S

    This is standard dynamic programming problem. Lets define state of dp solution.
    dp[i][j] ---> minimum cost of painting house till ith house when ith house is going to painted with jth color.

    We define the state , now lets define state corelation between each other.
    dp[i][currentColor] = Math.min(dp[i-1][firstDifferentColor]+ costs[i][currentColor],dp[i-1][secondDifferentColor]+costs[i][currentColor].

    Please find Java Code below

        public int minCost(int[][] costs) {
            // dp[i][j] ---> min cost occurred till ith element when ith house is going to paint with jth color.
    
            int[][] dp = new int[costs.length + 1][3];
            for(int[] i : dp) {
                Arrays.fill(i,0);
            }
    
    
    
            // if first house is colored with red
            dp[1][0]    =   costs[0][0];
            dp[1][1]    =   costs[0][1];
            dp[1][2]    =   costs[0][2];
            for(int row = 2 ; row < dp.length ; row++) {
    
                for(int col =   0; col < 3 ; col++) {
    
                    if(col  ==  0) {
                        dp[row][col] = Math.min(dp[row-1][col+1] * costs[row-1][col],dp[row-1][col+2] * costs[row-1][col]);
                    } else if(col == 1) {
                        dp[row][col] = Math.min(dp[row-1][col-1] * costs[row-1][col],dp[row-1][col+1] * costs[row-1][col]);
                    } else {
                        dp[row][col] = Math.min(dp[row-1][col-1] * costs[row-1][col],dp[row-1][col-2] * costs[row-1][col]);
                    }
                }
            }
    
            int answer = Integer.MAX_VALUE;
            for(int i : dp[dp.length-1]) {
                answer = Math.min(answer,i);
            }
            return answer;
        }
    

Log in to reply
 

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