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

Example

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.

Version 1. Up-Bottom

`//f[i][j] = Math.min(f[i-1][j-1], f[i-1][j])+grid[i][j]`
```public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
//O(n^2) space
//f[i][j] = Math.min(f[i-1][j-1], f[i-1][j])+grid[i][j]
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[size][size];
resultMap[0][0] = triangle.get(0).get(0);
for (int i = 1; i < size; i++) {
ArrayList<Integer> curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
if (j == 0) {
resultMap[i][j] = resultMap[i - 1][j] + curr.get(j);
} else {
if (j < triangle.get(i - 1).size()) {
resultMap[i][j] = Math.min(resultMap[i - 1][j - 1], resultMap[i - 1][j]) + curr.get(j);
} else {
resultMap[i][j] = resultMap[i - 1][j - 1] + curr.get(j);
}
}
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < size; i++) {
if (resultMap[size - 1][i] < min) {
min = resultMap[size - 1][i];
}
}
return min;
}```

Version 2. Bottom-Up O(n^2) space

```    public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[size][size];
//init the last row
ArrayList < Integer > lastRow = triangle.get(size - 1);
for (int i = 0; i < size; i++) {
resultMap[size - 1][i] = lastRow.get(i);
}
//from bottom to top
for (int i = size - 2; i >= 0; i--) {
ArrayList < Integer > curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
resultMap[i][j] = Math.min(resultMap[i + 1][j], resultMap[i + 1][j + 1]) + curr.get(j);
}
}
return resultMap[0][0];
}```

Version 3. Bottom-Up O(n) space

```    public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[2][size];
//init the last row
ArrayList < Integer > lastRow = triangle.get(size - 1);
for (int i = 0; i < size; i++) {
resultMap[(size - 1) % 2][i] = lastRow.get(i);
}
//from bottom to top
for (int i = size - 2; i >= 0; i--) {
ArrayList < Integer > curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
resultMap[i % 2][j] = Math.min(resultMap[(i + 1) % 2][j], resultMap[(i + 1) % 2][j + 1]) + curr.get(j);
}
}
return resultMap[0][0];
}```
Share