首页 > 代码库 > Triangle
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, where n is the total number of rows in the triangle.
思路：依次对每一层进行求解，使用数组记录当前层和上一层的结果。对于triangle[i][j]，其上层节点为triangle[i-1][j]和triangle[i-1][j+1]。
1 class Solution { 2 public: 3 int minimumTotal( vector<vector<int>> &triangle ) { 4 if( triangle.empty() ) { return 0; } 5 vector<vector<int>> totals( 2, vector<int>( triangle.size(), 0 ) ); 6 totals[0][0] = triangle[0][0]; 7 for( int i = 1; i < (int)triangle.size(); ++i ) { 8 vector<int> &prev = totals[(i-1)%2], &curr = totals[i%2]; 9 curr[0] = triangle[i][0] + prev[0];10 curr[i] = triangle[i][i] + prev[i-1];11 for( int k = 1; k < i; ++k ) {12 curr[k] = triangle[i][k] + min( prev[k-1], prev[k] );13 }14 }15 vector<int> &curr = totals[((int)triangle.size()-1)%2];16 int minTotal = curr[0];17 for( size_t i = 1; i != curr.size(); ++i ) {18 if( minTotal > curr[i] ) { minTotal = curr[i]; }19 }20 return minTotal;21 }22 };
上述方法采用的是自顶向下的求解策略，若采用自底向上的策略，我们可以获得更加简洁的代码：
1 class Solution { 2 public: 3 int minimumTotal( vector<vector<int>> &triangle ) { 4 if( triangle.empty() ) { return 0; } 5 vector<int> sum = triangle.back(); 6 for( size_t i = triangle.size()-1; i != 0; --i ) { 7 for( size_t k = 0; k != i; ++k ) { 8 sum[k] = triangle[i-1][k] + min( sum[k], sum[k+1] ); 9 }10 }11 return sum[0];12 }13 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。