Fast DP Java solution Runtime O(nk) space O(1)


  • 56
    T

    Explanation: dp[i][j] represents the min paint cost from house 0 to house i when house i use color j; The formula will be dp[i][j] = Math.min(any k!= j| dp[i-1][k]) + costs[i][j].

    Take a closer look at the formula, we don't need an array to represent dp[i][j], we only need to know the min cost to the previous house of any color and if the color j is used on previous house to get prev min cost, use the second min cost that are not using color j on the previous house. So I have three variable to record: prevMin, prevMinColor, prevSecondMin. and the above formula will be translated into: dp[currentHouse][currentColor] = (currentColor == prevMinColor? prevSecondMin: prevMin) + costs[currentHouse][currentColor].

    public class Solution {
    public int minCostII(int[][] costs) {
        if(costs == null || costs.length == 0 || costs[0].length == 0) return 0;
        
        int n = costs.length, k = costs[0].length;
        if(k == 1) return (n==1? costs[0][0] : -1);
        
        int prevMin = 0, prevMinInd = -1, prevSecMin = 0;//prevSecMin always >= prevMin
        for(int i = 0; i<n; i++) {
            int min = Integer.MAX_VALUE, minInd = -1, secMin = Integer.MAX_VALUE;
            for(int j = 0; j<k;  j++) {
                int val = costs[i][j] + (j == prevMinInd? prevSecMin : prevMin);
                if(minInd< 0) {min = val; minInd = j;}//when min isn't initialized
                else if(val < min) {//when val < min, 
                    secMin = min;
                    min = val;
                    minInd = j;
                } else if(val < secMin) { //when min<=val< secMin
                    secMin = val;
                }
            }
            prevMin = min;
            prevMinInd = minInd;
            prevSecMin = secMin;
        }
        return prevMin;
    }
    }

  • 5
    H

    A little suggestion, below code can be removed and still make the code working

    if(minInd< 0) {min = val; minInd = j;}//when min isn't initialized
    

  • 0
    Y

    i like this solution. I found that some people just check if value equals prevMIn, which is buggy. You also track the prevMinInd


  • 1
    C

    Excellent solution! Time complexity O(nk), space complexity O(1)


  • 0
    Y

    you are right, it will be implicitly initialized.


  • 0
    K

    Super algorithm....very clear after reading the explanation.


  • 0
    L
    if(minInd< 0) {min = val; minInd = j;}//when min isn't initialized
    

    this line is uesless?


  • 0
    R
    This post is deleted!

  • 0
    A

    @Tracy123 How does this work for a case where say there are 3 houses and 2 colors? Say house 1 picks the color 1, house 2 picks the color 2 and then house 3 has the cheapest color of 2 - this would allow for house 2's color to flip to 1 and then the solution is incorrect as you now have 2 adjacent houses (house 1 and 2) with the same color. Can someone please clarify if this solutions is correct for such cases?


Log in to reply
 

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