题解：
给出一个三角形，求从顶点到最底层的路径的最小和
方法：
动态规划
2个参数，i，j，代表从（i，j）出发直到底层的最小路径和。
f(i,j)=t[i][j]+min(f[i+1][j],f[i+1][j+1])
优化方案：
根据dp的方程可以发现，当前元素只与下一行的同列和右侧有关系，与左侧无关。那么优化思路就是只用1行，从左开始往右更新即可。这样就可以只用一维数组
dp[j]代表从某行（通过不断更新可更新成第1行）起的第j列开始，到底层的最小路径和
dp[j]=(i==t.size()-1)?t[i][j]:t[i][j]+min(dp[j],dp[j+1]) j从0到i去更新；i从倒数第一行向第1行去更新
思路：
首先三角形怎么处理？
不要被三角形迷惑，左对齐后，发现其实可以比较的对象就是下一行的同列，或者下一行的列数+1这两个元素。
然后是动态方程的设计
其实跟递归类似，就是找前后的递推关系，递归是设计了一个返回值，从要求解的值方向推导，直到迭代到初始条件就返回；dp是设计了一个数组，从初始值开始推导，一直推导到求解条件；
代码实现：
二维dp
class Solution {
public:
int minimumTotal(vector<vector<int>>& t) {
int n=t.size()-2;
for(int i=n;i>=0;i--)
for(int j=0;j<=i;j++)
t[i][j]+=min(t[i+1][j],t[i+1][j+1]);
return t[0][0];
}
};
优化成一维数组（通过观察dp方程）
class Solution {
public:
int minimumTotal(vector<vector<int>>& t) {
int n=t.size();
vector<int> dp(n,0);
for(int i=t.size()-1;i>=0;i--)
for(int j=0;j<=i;j++)
dp[j]=(i==t.size()-1)?t[i][j]:t[i][j]+min(dp[j],dp[j+1]);
return dp[0];
}
};
