首页 > 代码库 > Triangle(dp)
Triangle(dp)
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.
代码：空间复杂度O(n2)，可以改进。
class Solution {public: int minimumTotal(vector<vector<int> > &triangle) { int row=triangle.size(); int col=triangle[row-1].size(); int dp[row][col]; memset(dp,0,sizeof(dp)); int sum1=0;int sum2=0;int index=0; int res=(~(unsigned)1)>>1; for (int i = 0; i < row; ++i) { sum1+=triangle[i][0]; sum2+=triangle[i][index]; dp[i][0]=sum1; dp[i][index]=sum2; ++index; } for (int i = 1; i < row; ++i){ for (int j = 1; j < triangle[i].size()-1; ++j){ dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]; } } for(int i=0;i<col;++i){ if(dp[row-1][i]<res) res=dp[row-1][i]; } return res; }};
改进：因为每次只需上一次的结果，直接在原处覆盖就行，空间复杂度O(n)，用temp保留本次结果，并利用上次结果dp，求完本次之后，直接用temp覆盖dp，再进行下一次。
代码：
class Solution {public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) return 0; int row=triangle.size(); int col=triangle[row-1].size(); vector<int> dp(col,0); vector<int> temp(col,0); int sum1=0;int sum2=0;int index=0; int res=(~(unsigned)1)>>1; dp[0]=triangle[0][0]; for (int i = 1; i < row; ++i){ temp.resize(col,0); for (int j = 0; j < triangle[i].size(); ++j){ if(j==0) temp[j]=dp[j]+triangle[i][j]; else if(j==triangle[i].size()-1) temp[j]=dp[j-1]+triangle[i][j]; else temp[j]=min(dp[j-1],dp[j])+triangle[i][j]; } dp=temp; } for(int i=0;i<col;++i){ if(dp[i]<res) res=dp[i]; } return res; }};
Triangle(dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。