Java minCurr[i] = costs[i][j] + min(minLeft[i], minRight[i]) : O(k) space, O(nk) Runtime


  • 0
    V
    public class Solution {
        public int minCostII(int[][] costs) {
            int n = costs.length, minCost = 0;
            
            if (n > 0) {
                int k = costs[0].length;
                int[] dp = new int[k];
                for (int i = 0; i < k; i++) dp[i] = costs[0][i];
                
                for (int i = 1; i < n; i++) {
                    int[] tmp = new int[k];
                    int[] minLeft = new int[k];
                    int[] minRight = new int[k];
                    minLeft[0] = minRight[k - 1] = Integer.MAX_VALUE;
                    
                    for (int j = 1; j < k; j++) {
                        minLeft[j] = Math.min(minLeft[j - 1], dp[j - 1]);
                        minRight[k - 1 - j] = Math.min(minRight[k - j], dp[k - j]);
                    }
                    
                    for (int j = 0; j < k; j++) {
                        tmp[j] = Math.min(minLeft[j], minRight[j]) + costs[i][j];
                    }
                    
                    dp = tmp;
                }
    
                minCost = dp[0];
                for (int i = 1; i < k; i++) {
                    minCost = Math.min(dp[i], minCost);
                }
            }
            
            return minCost;
        }
    }
    

Log in to reply
 

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