首页 > 代码库 > [leetcode]Triangle
[leetcode]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 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, wheren is the total number of rows in the triangle.
基本思想:
构造一个与给定三角形同样形状的三角形,每个节点记录从根到这个节点的最小路径。
计算每个节点的从根最小距离只依赖于上面节点的状况:
- 节点是最左节点, f[i][0] = f[i-1][0] + triangle[i][0] (i >=1)
- 节点是最右节点, f[i][j] = f[i-1][j-1] +triangle[i][j]
- 节点是中间节点, f[i][j] = min(f[i-1][j-1],f[i-1][j]) + triangle[i][j]
由此可以依次计算出每个节点的最小路径。
如果记录整个三角形需要O(n^2)的空间。 但是由于每行的计算只依赖于上一行的内容,所以空间复杂度可以只用O(n)。
代码:
int minimumTotal(vector<vector<int> > &triangle) { // c++ int rows = triangle.size(); //check null if(rows == 0) return 0; vector<int> record(rows,triangle[0][0]); int prej; //use prej to record record[j-1] before update //tmp remember record[j] before update; for(int i = 1; i < triangle.size(); i++) for(int j = 0; j < triangle[i].size(); j++){ if(j == 0){ prej = record[j]; record[j] += triangle[i][j]; } // record[j] = record[j-1] + triangle[i][j]; else if(j == triangle[i].size()-1){ int tmp = record[j]; record[j] = prej + triangle[i][j]; prej = tmp; } // record[j] = ((record[j] < record[j-1])? record[j] : record[j-1]) + triangle[i][j]; else{ int tmp = record[j]; record[j] = ((record[j] < prej)? record[j] : prej) + triangle[i][j]; prej = tmp; } } //find minmum int min = record[0]; for(int i = 1; i < record.size(); i++) if(record[i] < min) min = record[i]; return min; }
[leetcode]Triangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。