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

``````class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
if(triangle.size()==0)
return 0;
//初始化res的值
res = 0;
for(int i = 0;i < triangle.size();i++)
res += triangle[i][0];
findMin(triangle,0,0,0);
return res;
}
void findMin(vector<vector<int> > &triangle,int index,int line,int sum){
if(line >= triangle.size()){
res = res < sum ? res : sum;
return ;
}
sum += triangle[line][index];
findMin(triangle,index,line+1,sum);
sum -= triangle[line][index];
if(line == 0)
return;
sum += triangle[line][index+1];
findMin(triangle,index+1,line+1,sum);
}
private:
int res;
};``````

``````class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
if(triangle.size()==0)
return 0;
//初始化res的值
int n = triangle.size();
for(int i = 1;i < n;i++){
for(int j = 0;j < triangle[i].size();j++){
if(j==0){
triangle[i][j] += triangle[i-1][j];
}else if(j == triangle[i].size()-1)
triangle[i][j] += triangle[i-1][j-1];
else{
int min = triangle[i-1][j] > triangle[i-1][j-1] ? triangle[i-1][j-1] : triangle[i-1][j];
triangle[i][j] += min;
}
}
}
int res = triangle[n-1][0];
for(int i = 1;i < triangle[n-1].size();i++){
res = res > triangle[n-1][i] ? triangle[n-1][i] : res;
}
return res;
}
};``````

``````class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (triangle.size() == 0)
return 0;

vector<int> f(triangle[triangle.size()-1].size());

f[0] = triangle[0][0];
for(int i = 1; i < triangle.size(); i++)
for(int j = triangle[i].size() - 1; j >= 0; j--)
if (j == 0)
f[j] = f[j] + triangle[i][j];
else if (j == triangle[i].size() - 1)
f[j] = f[j-1] + triangle[i][j];
else
f[j] = min(f[j-1], f[j]) + triangle[i][j];

int ret = INT_MAX;
for(int i = 0; i < f.size(); i++)
ret = min(ret, f[i]);

return ret;
}
};``````