Leetcode 120. Triangle

2019-11-14 10:43:41

字体：大中小

来源：转载

供稿：网友

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 is 11 (i.e., 2 + 3 + 5 + 1 = 11).

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

s思路： 1. 最小路径和，从上往下，下面的数的坐标只能是上一个数的坐标或坐标加1。枚举所有路径，然后找出最小值？ 2. 枚举代码功能正确，但是TLE?那必须是大量重复计算所致。分析如下：这里写图片描述如上图，2到5的路径有多条，也就是说从5开始往下遍历需要遍历多次，这就重复计算了！完全可以从上往下计算到每个位置的最小和，然后不断迭代进行，也就是在每个位置计算最小和保存起来。这就是DP的思路！ 3. 以后做recursive的题，先看看是否会有重复计算，如有，则用DP！！

//方法1：recursive的枚举所有路径。TLE?class Solution {public: void helper(vector<vector<int>>& triangle,int level,int pos,int&path,int cur){ if(level==triangle.size()){ path=path<cur?path:cur; return; } helper(triangle,level+1,pos,path,cur+triangle[level][pos]); if(pos+1<triangle[level].size()) helper(triangle,level+1,pos+1,path,cur+triangle[level][pos+1]); } int minimumTotal(vector<vector<int>>& triangle) { // int path=INT_MAX; helper(triangle,0,0,path,0); return path; }};//方法2：dpclass Solution {public: int minimumTotal(vector<vector<int>>& triangle) { // int n=triangle.size(); int path=INT_MAX; for(int i=1;i<n;i++){ triangle[i][0]+=triangle[i-1][0]; triangle[i][i]+=triangle[i-1][i-1]; for(int j=1;j<i;j++){ triangle[i][j]+=min(triangle[i-1][j],triangle[i-1][j-1]); } } for(int i=0;i<n;i++){ path=min(path,triangle[n-1][i]); } return path; }};

上一篇：[BZOJ2055]80人环游世界（有源汇有上下界的费用流）

下一篇：LEETCODE--Best Time to Buy and Sell Stock II

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注