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).
给定一个三角形二元数组，求从头节点到叶子结点的最短路径。
动态规划，将triangle[i][j]赋值为直到triangle[i][j]节点时的最短路径长度，则可以分成三个部分考虑：
（1）ij在三角形最左侧，则triangle[i][j] += triangle[i-1][j]
（2）ij在三角形最右侧，则triangle[i][j] += triangle[i-1][j-1]
（3）ij在中间，则triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
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{
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
}
}
}
int res;
if(n>0) res = triangle[n-1][0];
for(int k=0; k<triangle[n-1].size(); k++){
res = min(res, triangle[n-1][k]);
}
return res;
}
};
