Question
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Solution
Use dynamic programming
Code
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size() == 0) return 0;
List<List<Integer>> minCache = new ArrayList<>();
minCache.add(new ArrayList<>(triangle.get(0)));
for(int i=1; i<triangle.size(); i++) {
List<Integer> prevLayer = minCache.get(i-1);
List<Integer> curLayer = new ArrayList<>();
minCache.add(curLayer);
List<Integer> triLayer = triangle.get(i);
for(int j=0; j<triLayer.size(); j++) {
int val = triLayer.get(j);
int choice = Integer.MAX_VALUE;
if(j-1 >= 0) choice = Math.min(choice, prevLayer.get(j-1) + val);
if(j < prevLayer.size()) choice = Math.min(choice, prevLayer.get(j) + val);
curLayer.add(choice);
}
}
int min = Integer.MAX_VALUE;
List<Integer> lastLayer = minCache.get(minCache.size()-1);
for(int i=0; i<lastLayer.size(); i++) {
min = Math.min(lastLayer.get(i), min);
}
return min;
}
}
Performance
O(N)