描述：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
解答：
本条题目可以采用递归，也可以采用动态规划的方法来解决。递归的话，每个节点到叶节
点的最小距离为其下方两个相邻节点的最小距离当中的最小值。
采用动态规划算法的话，则初状态的话为最后一行，最短距离为自身。然后逐行向上推导，
推导出每个位置的最小距离，返回的最后结果为首行的第一个元素。可以使用二位数组来保存
结果，也可以使用滚动数组来保存节点，下面给出二维数组保存结果的代码:
class Solution { public: //本条题目可采用动态规划的方法 //自底向下进行递推 int minimumTotal(vector<vector<int>>& triangle) { vector<vector<int>> res=triangle; //结果当中的所有行数 int rows=res.size(); //从倒数第二行开始推导 for(int i=rows-2;i>=0;i--){ for(int j=0;j<i+1;j++) res[i][j]+=min(res[i+1][j],res[i+1][j+1]); } return res[0][0]; } };
还可以使用滚动数组来保存代码，从而降低空间复杂度。集体代码如下：
class Solution { public: //本条题目可采用动态规划的方法 //自底向下进行递推，使用滚动数组来节省空间 int minimumTotal(vector<vector<int>>& triangle) { int len=triangle.size(); //使用最后一行来初始化当前的结果 vector<int> res(triangle[len-1]); //首先要控制循环的次数，然后控制内循环的范围 for(int i=len-1;i>=1;i--){ for(int j=0;j<i;j++) //当前的值加上上一次结果当中较小的值 res[j]=triangle[i-1][j]+min(res[j],res[j+1]); } return res[0]; } };
原文：https://www.cnblogs.com/wangkaia/p/12003598.html