Java DP O(n*k) Time O(k) Space Solution


  • 0
    public int minCost(int[][] costs) {
    	if (costs == null || costs.length == 0) {
    		return 0;
    	}
    	int n = costs.length;
    	int[] prev = new int[3], cur = new int[3];
    	prev = costs[0];
    	for (int i = 1; i < n; i++) {
    	    cur = new int[3];
    		for (int j = 0; j < 3; j++) {
    			cur[j] = costs[i][j] + Math.min(prev[(j + 1) % 3], prev[(j + 2) % 3]);
    		}
    		prev = cur;
    	}
    	return Math.min(prev[0], Math.min(prev[1], prev[2]));
    }

Log in to reply
 

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