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).
The problem has tree like structure, which would lead to solve the problem using DFS solution. However each adjacent node share a overlapping branch. The traversal can use done using bottom-up or top-down approach.
If you decide to use top-down approach then the same path may be repeated again and to optimize the computation, one need to maintain cache with sum of already visited path. However, you will need a cache that is at least the same size as the input triangle itself to store the pathsum, which takes O(N^2) space.
Bottom-up approach is pretty straightforward. For the last row the minimum sum of nodes will be the value of node itself. For minimum pathsum at ith node in row k will be the sum of ith node with the minimum value of its children in the row after the k.
minSum[k][i] = Math.min(minsum[k+1][i-1], minsum[k+1][i+1]) + triangle[k][i]
public class Triangle {
public static void main(String[] args) {
List l1 =Arrays.asList(new int[]{2});
List l2 =Arrays.asList(new int[]{3,4});
List l3 =Arrays.asList(new int[]{6,5,7});
List l4 =Arrays.asList(new int[]{4,1,8,3});
List l5 = new ArrayList();
l5.add(l1);l5.add(l2);l5.add(l3);l5.add(l4);
System.out.println(new Triangle().minimumTotal(l5));
}
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle.size() == 0)
return 0;
for (int i = triangle.size() - 2; i >= 0; i--) {
List<Integer> row = triangle.get(i);
List<Integer>prevRow = triangle.get(i + 1);
for (int j = 0; j < row.size(); j++) {
int value = row.remove(j) + Math.min(prevRow.get(j), prevRow.get(j+1));
row.add(j, value);
}
}
return triangle.get(0).get(0);
}
}