leetCode(47):Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[[2],[3,4], [6,5,7], [4,1,8,3]]

The minimum path sum from top to bottom is11(i.e.,2+3+5+1= 11).

Note:Bonus point if you are able to do this using onlyO(n) extra space, wherenis the total number of rows in the triangle.

动态规划，其实和二叉树的最小路径有点像，，确实完全可以先转化成二叉树再求最小路径，不过会比较麻烦。先是直观一点的（方法应该是正确的，但时间越限了）：

class Solution {public: int sum(vector<vector<int>>& triangle,int row,int low){if(row==triangle.size()-1){return triangle[row][low];}else{<span style="white-space:pre"></span>//当前值加上下一行的两个值对应的较小路径，仔细观察可知，递归的时候有重复计算，所以是可以改进的。return triangle[row][low]+min(sum(triangle,row+1,low),sum(triangle,row+1,low+1));}}int minimumTotal(vector<vector<int>>& triangle) {if(triangle.size()==0 || triangle[0].size()==0)return 0;return sum(triangle,0,0);}};改进方法如下：

class Solution {public: //本程序改变了输入的数组，如果有要求的话可以先将输入数组复杂int minimumTotal(vector<vector<int>>& triangle) {if(triangle.size()==0 || triangle[0].size()==0)return 0;for(int i=triangle.size()-2;i>=0;–i){//从底层开始算起，本层的值等于当前值加上下一层的较小者for(int j=0;j<triangle[i].size();++j){//这里用到了标准库内的函数triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1]);}}//返回第一行的第一个值即最小路径return triangle[0][0];}};

只剩下一条路，那就是成功的路。