Leetcode 120. Triangle

2019-11-14 12:06:36

字體：大中小

來源：轉載

供稿：網友

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; }};

上一篇：數據結構之簡單算法學習

下一篇：[BZOJ1584][Usaco2009 Mar]Cleaning Up 打掃衛生（dp+數學相關優化）