O(n) space solution, Java


  • 0
    J
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[] mins = new int[len];
        mins[0] = triangle.get(0).get(0);
        for(int i=1; i<len; i++) {
        	mins[i] = mins[i-1] + triangle.get(i).get(i);
        	for(int j=i-1; j>0; j--) {
        		mins[j] = Math.min(mins[j], mins[j-1]) + triangle.get(i).get(j);
        	}
        	mins[0] = mins[0] + triangle.get(i).get(0);
        }
        int min = Integer.MAX_VALUE;
        for(int x : mins) {
        	if(x < min)
        		min = x;
        }
        return min;
    }
    

    To use only O(n) space, we can only keep track of minimal values ending on the ith row. here mins[j] stands for the minimal path sum ending on the jth element in the ith row. You have to update backwards so previous updates won't affect later ones.


Log in to reply
 

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