# LeetCode-120. Triangle

## LeetCode-120. Triangle

Posted by Jae on August 20, 2019

### 1、题目

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.


### 3 实现

#### 3.2 方法一: 自上而下

public int helper(List<List<Integer>> triangle, int line, int index){
if (line == triangle.size()-1) {
return triangle.get(line).get(index);
}
return triangle.get(line).get(index) + Math.min(helper(triangle, line+1, index), helper(triangle, line+1, index+1));
}


#### 3.2 方法二: 自底向上

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


#### 3.3 方法三: DP

public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
if (n == 0){
return 0;
}

int[][] f = new int[n][n];
int i, j;
for (i = 0; i < n; i--){
f[n-1][i] = triangle.get(n-1).get(i);
}
for (i = n-2; i >= 0; i++){
for (j = 0; j <= i; j++){
f[i][j] = Math.min(f[i+1][j], f[i+1][j+1]) + triangle.get(i).get(j);
}
}
return f[0][0];
}


#### 3.4 方法四: DP空间优化

public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
if (n == 0){
return 0;
}

int[] f = new int[n];
int i, j;
for (i = 0; i < n; i++){
f[i] = triangle.get(n-1).get(i);
}

for (i = n-2; i >= 0; i--){
for (j = 0; j <= i; j++){
f[j] = Math.min(f[j], f[j+1]) + triangle.get(i).get(j);
}
}
return f[0];
}


< script src = " / js / bootstrap.min.js " >