5 ms java solution with O(KN)


  • 2
    J
    public int minCostII(int[][] costs) {
        if(costs == null || costs.length == 0 || costs[0].length == 0)  return 0;
        int k = costs[0].length;
        int[] dp = new int[k];
        int m1 = 0, m2 = 0;
        for(int i = costs.length - 1; i >= 0; i--){
            int[] tempdp = new int[k];
            int mm1 = m1, mm2 = m2;
            m1 = Integer.MAX_VALUE; m2 = Integer.MAX_VALUE;
            for(int j = 0; j < k; j++){
                tempdp[j] = (dp[j] == mm1 ? mm2 : mm1) + costs[i][j];
                if(tempdp[j] < m1){
                    m2 = m1;
                    m1 = tempdp[j];
                }
                else
                    m2 = Math.min(m2, tempdp[j]);
            }
            dp = tempdp;
        }
        return m1;
    }

  • 0
    Y

    Hi Jinx_boom, I think there is a bug in your solution. dp[j] == mm1 , this check is not enough since different colors may lead to the same dp[j]. Therefore, you may need to add a minColor variable as well as a temp for minColor in the for loop.


  • 0
    J

    If you are talking about different colors sharing the same minimum cost, mm2 will be the min cost from other color.


Log in to reply
 

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