一、问题描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
题目链接：三角形最小路径和
二、题目要求
样例
输入：triangle= [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11解释：如下面简图所示：2346574183自顶向下的最小路径和为11（即，2+3+5+1=11）。
考察
动态规划中等题型 建议用时15~30min
三、问题分析
上面的数字三角形不好观察，我给你对齐一下位置，如下：
[2] [3,4] [6,5,7] [4,1,8,3]
是不是和杨辉三角的存储结构差不多啊！接下来接着用用我们的三步走，老套路了：
第一步 含义搞懂：
这明显是二维数组的动态规划，那么就用dp[i][j]存储，那么这代表什么含义？
题目要求从上到下的最小花费，可以走下一行同一列、下一行多一列的方向。一开始我从上向下判断，突然发现多出很多条件，不能走的地方要单独考虑，后来发现从下向上走更加简单，于是屁颠屁颠改了算法。
下次，考虑问题我一定要反着想。
那么dp[i][j]就代表从最下面到当前位置，最小花费数目。
第二步 变量初始：
最后一行，没有下面了，所以这一行统统初始化。
for(j=0;j<n;j++)//只赋值最后一行的dp[n-1][j]=triangle[n-1][j];
第三步 规律归纳：
[2] [2+3+5+1 ] [3,4] [3+5+14+5+1 ] [6,5,7] [6+15+17+3 ] [4,1,8,3] [4183]
左侧是给定的数据，右侧是动态规划后每一步的结果，大家有没有发现什么规律。
比如倒数第二行的6，可以由下一行的4 1得到，选一个小的1 倒数第二行的5，可以由下一行的1 8得到，选一个小的1
上面也是相同的算法，规律出现：
dp[i][j]=triangle[i][j]+min(dp[i+1][j],dp[i+1][j+1]);
三步走，打完收工！
四、编码实现
classSolution { public: intminimumTotal(vector<vector<int>>&triangle) { longlonginti,j,n=triangle.size();//初始化变量longlongintdp[n+1][n+1]; for(j=0;j<n;j++)//动态规划变量初始dp[n-1][j]=triangle[n-1][j]; for(i=n-2;i>=0;i--) { for(j=0;j<=i;j++) { dp[i][j]=triangle[i][j]+min(dp[i+1][j],dp[i+1][j+1]);//规律归纳 } } returndp[0][0];//输出结果 } };
