给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[[2],[3,4],[6,5,7],[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
算法分析：
本题是动态规划，最基本的办法是自底向上递推，从最后一行向上递推，因为每个点有两个选择，向下或者向右下，所以求出这两种情况下点到下一行的路径累加和，取其中较小的值，再逐步向上递推，求出顶结点到最后一行的最小路径和。设置一个二维数组f[n][n]，来保存第n行第n个结点到最后一行的最小路径，其中数组的最下面一行的值就是所给数据的底层行的值。从倒二行出发，求出两种选择情况下每个点到最底行的最小路径和，将这个值保存到数组中。逐步向上面一行递推，递推方程为：
f[i][j]=min(f[i+1][j],f[i+1][j+1])
最后返回顶结点的值即可。代码如下：
class Solution {
public:int mi(int a,int b){return a<b?a:b;}int minimumTotal(vector<vector<int>>& triangle){int res=0;int m=triangle.size();int n=triangle[m-1].size();int f[m][n];for(int i=0;i<n;i++)f[m-1][i]=triangle[m-1][i];for(int i=m-2;i>=0;i--)for(int j=0;j<triangle[i].size();j++)f[i][j]=mi(f[i+1][j],f[i+1][j+1])+triangle[i][j];return f[0][0];}
};但是这种方法比较浪费空间，好多点的值求出之后都不会用到了，为了节省空间，我们可以将那些有用的值覆盖掉无用值。定义一个一维数组f[n]，表示每一行的每个点到最底行的最小路径和。初始值就是所给数据中最底一行的值。从倒二行出发，还是上面所讲的思路，求出每个点到下面一行的最小路径和，然后将这一行的值覆盖掉原来的值，因为求出倒二行的最小路径和后倒一行的值就没有用了。还是自底向上递推，将每一行的值覆盖点前一行的值，最后返回数组首元素即可。代码如下：
class Solution {
public:int mi(int a,int b){return a<b?a:b;}int minimumTotal(vector<vector<int>>& triangle){int m=triangle.size();int f[m];for(int i=0;i<m;i++)f[i]=triangle[m-1][i];for(int i=m-1;i>=0;i--)for(int j=0;j<i;j++)f[j]=mi(f[j],f[j+1])+triangle[i-1][j];return f[0];}
};