Accepted Simple JAVA O(NK) solution


  • 9
    R
    public class Solution {
        public int minCostII(int[][] costs) {
            if (costs.length == 0 || costs[0].length == 0) {
                return 0;
            }
            int m = costs.length, n = costs[0].length, m1 = 0, m2 = 0;
            int[] dp = new int[n];
            for (int i = 0; i < m; i++) {
                int t1 = m1, t2 = m2;
                m1 = Integer.MAX_VALUE;
                m2 = Integer.MAX_VALUE;
                for (int j = 0; j < n; j++) {
                    dp[j] = (dp[j] == t1 ? t2 : t1) + costs[i][j];
                    if (m1 <= dp[j]) {
                        m2 = Math.min(dp[j], m2);
                    }
                    else {
                        m2 = m1;
                        m1 = dp[j];
                    }
                }
            }
            
            return m1;
        }
    }

  • 0
    Y

    Hi rjr130, I think the check dp[j] == t1 is not enough. there are cases where the value equals min yet the color is different. in that case, it is still ok to take t1.


  • 0
    Y

    Agree here, should check the previous color as well. The test case happens to pass


  • 0
    R

    In that case then t2 would have the same value as t1. So it will still work. Please feel free to correct me if I was wrong.


Log in to reply
 

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