# Triangle

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.

## Analysis

DP vs DFS / BFS

`O(1)` 时间复杂度的递推关系 `minpath[k][i] = min( minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];`

Top-Down vs Bottom-Up

LeetCode论坛分析 @stellari：

• For 'top-down' DP, starting from the node on the very top, we recursively find the minimum path sum of each node. When a path sum is calculated, we store it in an array (memoization); the next time we need to calculate the path sum of the same node, just retrieve it from the array. O(N^2) space.

• 'Bottom-up' DP, on the other hand, is very straightforward: we start from the nodes on the bottom row; the min pathsums for these nodes are the values of the nodes themselves. From there, the min pathsum at the ith node on the kth row would be the lesser of the pathsums of its two children plus the value of itself.

Or even better, since the row minpath[k+1] would be useless after minpath[k] is computed, we can simply set minpath as a 1D array, and iteratively update itself:

``````For the kth level:
minpath[i] = min( minpath[i], minpath[i+1]) + triangle[k][i];
``````

``````triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
``````

## Solution

DP Buttom Up 1D array (4ms 90.59% AC)

``````class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int size = triangle.size();

int[] minpath = new int[size];
int k = 0;
for (Integer e : triangle.get(size - 1)) {
minpath[k++] = e;
}
for (int row = size - 2; row >= 0; row--) {
for (int i = 0; i <= row; i++) {
minpath[i] = Math.min(minpath[i], minpath[i + 1]) + triangle.get(row).get(i);
}
}
return minpath[0];
}
}
``````

*DP - Bottom Up - Improved implementation with size = N + 1 array (4ms 90.59% AC)

``````class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int size = triangle.size();

int[] minpath = new int[size + 1];
for (int row = size - 1; row >= 0; row--) {
for (int i = 0; i <= row; i++) {
minpath[i] = Math.min(minpath[i], minpath[i + 1]) + triangle.get(row).get(i);
}
}
return minpath[0];
}
}
``````

DP with O(1) space

``````public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
for(int i = triangle.size() - 2; i >= 0; i--)
for(int j = 0; j <= i; j++)
triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
return triangle.get(0).get(0);
}
}
``````

Top Down DP with memorization - DFS (102 ms 1.05% AC)

``````class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) return 0;
return minPathSumHelper(triangle, new HashMap<String, Integer>(), new Coordinate(0, 0));
}
public int minPathSumHelper(List<List<Integer>> triangle, HashMap<String, Integer> map, Coordinate cor) {
String key = cor.row + "," + cor.col;
if (map.containsKey(key)) {
return map.get(key);
}
if (cor.row >= triangle.size() || cor.col >= triangle.get(triangle.size() - 1).size()) return 0;
int val = triangle.get(cor.row).get(cor.col);
int min = val +
Math.min(minPathSumHelper(triangle, map, new Coordinate(cor.row + 1, cor.col)),
minPathSumHelper(triangle, map, new Coordinate(cor.row + 1, cor.col + 1)));
map.put(key, min);
return min;
}

class Coordinate {
int row, col;
Coordinate (int row, int col) {
this.row = row;
this.col = col;
}
}
}
``````

## Reference

https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle