Java DP solution without modify the original array O(2k) space


  • 0
    G
    public int minCostII(int[][] costs) {
    	if (costs == null || costs.length == 0)
    	    return 0;
    	int m = costs.length;
    	int k = costs[0].length;
    
    	// Two rows to store temporary result
    	int[][] dp = new int[k][2];
    	int pre = 0, next = 1;
    	for (int i = 0; i < m; i++) {
    	    for (int j = 0; j < k; j++) {
    		dp[j][next] = costs[i][j] + getMin(dp, j, pre);
    	    }
                pre = 1 - pre;
                next = 1 - next;
    	}
    	return getMin(dp, -1, m % 2 == 0 ? 0 : 1);
        }
    
        private int getMin(int[][] array, int exclude, int column) {
    	int min = Integer.MAX_VALUE;
    	for (int i = 0; i < array.length; i++) {
    	    if (i == exclude)
    		continue;
    	    min = Math.min(min, array[i][column]);
    	}
    	return min == Integer.MAX_VALUE ? 0 : min;
        }

Log in to reply
 

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