Ac solution code


  • 0

    The basic idea is using DP algorithm to choose the minimum cost from (i - 1) house, then add it to costs[i][j] as minCosts[i][j] (To save space, we save minCosts[i][j] to costs[i][j] directly). A trick is to store two columns of top 2 minimum costs of (i - 1) row, to ensure we can choose one column isn't equal to j.

    Runtime complexity = O(nk)

    public int minCostII(int[][] costs) {
    	if (costs == null || costs.length == 0) return 0;
    	int n = costs.length, k = costs[0].length;
    	int min1 = -1, min2 = -1; 
    	for (int i = 0; i < n; i++) {
    		int lastmin1 = min1, lastmin2 = min2;
    		min1 = min2 = -1;
    		for (int j = 0; j < k; j++) {
    			// Choose the index of the minimum cost from i - 1 row (exclude i)
    			if (lastmin1 != j)
    				costs[i][j] += (lastmin1 == -1) ? 0 : costs[i - 1][lastmin1];// Choose lastMin1
    			else
    				costs[i][j] += (lastmin2 == -1) ? 0 : costs[i - 1][lastmin2];// Choose lastMin2
    			
    			if (min1 == -1 || costs[i][min1] > costs[i][j]) {// Update min1
    				min2 = min1;
    				min1 = j; 
    			} else if (min2 == -1 || costs[i][min2] > costs[i][j]) {// Update min2
    				min2 = j;
    			}
    		}
    	}
    	return costs[n-1][min1];
    }

Log in to reply
 

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