JAVA DP Solution (With Explanation)


  • 0
    T
    class Solution {
        //Dynamic programming
        //I use OPT[i][0] represents the lowest cost to paint first i houses and paint the last house with red color.
        //I use OPT[i][1] represents the lowest cost to paint first i houses and paint the last house with blue color.
        //I use OPT[i][2] represents the lowest cost to paint first i houses and paint the last house with green color.
        /*We have the following fomula*/
        /*OPT[i][0] = Math.min(OPT[i-1][1], OPT[i-1][2]) + costs[i][0];
        /*OPT[i][1] = Math.min(OPT[i-1][0], OPT[i-1][2]) + costs[i][1];
        /*Opt{i}[2] = Math.min(OPT[i-1][0], OPT[i-1][1]) + costs[i][2];
        */
        public int minCost(int[][] costs) {
            int[] lastCosts = new int[3];
            for(int i = 0; i <= costs.length-1; i++){
                int first = Math.min(lastCosts[1], lastCosts[2]) + costs[i][0];
                int second= Math.min(lastCosts[0], lastCosts[2]) + costs[i][1];
                int third = Math.min(lastCosts[0], lastCosts[1])+  costs[i][2];
                lastCosts[0] = first;
                lastCosts[1] =second;
                lastCosts[2] = third;
            }
            lastCosts[0] = Math.min(lastCosts[0], lastCosts[1]);
            lastCosts[0] = Math.min(lastCosts[0], lastCosts[2]);
            return lastCosts[0];
        }
    }

Log in to reply
 

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