# Java - Top Down DP Solution - No Extra Space

• [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);
}``````

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