给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
[ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
https://leetcode-cn.com/problems/triangle/
https://blog.csdn.net/wodemaoheise/article/details/107350930
方法：动态规划
这道题的状态转移方程其实很好想，采用备忘录的方式，用局部最优解出全局最优。
dp[i][j] 表示从点 (i,j)到底边的最小路径和，
dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]。
据说本题是一道非常经典且历史悠久的动态规划题，其作为算法题出现，最早可以追溯到 1994 年的 IOI（国际信息学奥林匹克竞赛）的 The Triangle。时光飞逝，经过 20 多年的沉淀，往日的国际竞赛题如今已经变成了动态规划的入门必做题。
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。 int** dp = new int*[n + 1]; for(int i=0;i<=n;++i){ dp[i] = new int[n+1]; memset(dp[i],0,sizeof(int)*(n+1)); } // 从三角形的最后一行开始递推。 for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]; } } return dp[0][0]; } };
