# 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:

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