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:


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();
    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);