给出一个三角形（数据数组），找出从上往下的最小路径和。每一步只能移动到下一行中的相邻结点上。
比如，给你如下三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
则从上至下最小路径和为 11（即，2 + 3 + 5 + 1 = 11）
注意：
加分项：如果你可以只使用 O(n) 的额外空间（n是三角形的行数）。
详见：https://leetcode.com/problems/triangle/description/
方法一：
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=triangle[n-1][0];
for(int i=1;i<triangle[n-1].size();++i)
{
res=min(res,triangle[n-1][i]);
}
return res;
}
};
方法二：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n=triangle.size();
vector<int> dp(triangle.back());
for(int i=n-2;i>=0;--i)
{
for(int j=0;j<=i;++j)
{
dp[j]=min(dp[j],dp[j+1])+triangle[i][j];
}
}
return dp[0];
}
};
参考：https://www.cnblogs.com/grandyang/p/4286274.html