Java - Top Down DP Solution - No Extra Space


  • 1

    [NOTE] - Assumption here is that input can be modified to save space
    :)

    The Logic here is to calculate the min values at each level and carry over.

    Start with second level : List<Integer> cur = triangle.get(i);

    Update each of the values with new values.
    New values depends on min of previous level's two values: the one directly above it (say prev[j]) and the one next to this (prev[j-1]) . This is calculated here :

    int minSum = cur.get(j) + getPreviousMin(j, prev);

    Ex: In 3rd level of the example, the value of the middle(ie 5) is min of value at above level's 3 and 4.

    /*[
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
    ]*/
    

    Hope this helps.

    public int minimumTotal(List<List<Integer>> triangle) {
        List<Integer> prev = triangle.get(0);
        int min = prev.get(0);
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> cur = triangle.get(i);
            min = Integer.MAX_VALUE;
            for(int j = 0; j < cur.size(); j++) {
                int minSum = cur.get(j) + getPreviousMin(j, prev);
                cur.set(j,minSum);
                if(minSum < min) min = minSum;
            }
            prev = cur;
        }
        return min; 
    }
    
    private int getPreviousMin(int j, List<Integer> prev) {
        int m1 = (j>=prev.size())?Integer.MAX_VALUE : prev.get(j);
        int m2 = (j<=0)? Integer.MAX_VALUE : prev.get(j-1);
        return Math.min(m1, m2);
    }

Log in to reply
 

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