问题：三角形，从顶到底最小路径
解法类型：DP动态规划
思路：
最原始思路：穷举每一行每个点的最小路径值，下一行=上一行累计，形成2维数组（n*n），再从数组最后一行选取最小值。
进化思路：每行计算，只需要上一行的结果，则只需要2维数组（2*n）两行保存数据即可。
再进化思路：如何化为只需要1维数组，则需计算值不覆盖接下来要计算的值，即从后往前计算。（原来从顶到底->从底到顶）
每个点的路径 = 本点值 + 下一行的两个中最小的 dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
代码参考：
1 class Solution { 2 public: 3 int minimumTotal(vector<vector<int>>& triangle) { 4 vector<int> dp(triangle[triangle.size()-1]); 5 int i, j; 6 for(i=triangle.size()-2; i>=0; i--){ 7 for(j=0; j<triangle[i].size(); j++){ 8 dp[j] = triangle[i][j] + min(dp[j], dp[j+1]); 9 } 10 } 11 return dp[0]; 12 } 13 };
原文：https://www.cnblogs.com/habibah-chang/p/12316773.html