首页 > 代码库 > leetcode Triangle
leetcode Triangle
给定一个三角数组，找从上到下的最小和，例如：
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).
思路一，DP， 在原三角数组中操作，每层更新为到该层的最小距离，然后返回最后一层的最小即可。
class Solution {public:int minimumTotal(vector<vector<int> > &triangle){ int row = triangle.size(), ans = INT_MAX; if (row == 0) return 0; for (int i = 1; i < row; ++i) { triangle[i][0] = triangle[i-1][0] + triangle[i][0]; for (int j = 1; j < triangle[i].size() - 1; ++j) { triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]; } triangle[i][triangle[i].size()-1] = triangle[i-1][triangle[i-1].size()-1] + triangle[i][triangle[i].size()-1]; } for (int i = 0; i < triangle[row-1].size(); ++i) { if (triangle[row-1][i] < ans) ans = triangle[row-1][i]; } return ans;}};
思路二，不改变原来数组，类似上一题，另建空间O(row)来存到当前行的最优，然后根据数组来更新这个最优数组，然后在数组中返回最小的值。
class Solution {public:int minimumTotal(vector<vector<int> > &triangle){ int ans = INT_MAX, row = triangle.size(), pre; if (row == 0) return ans; vector<int> tmp; tmp.push_back(triangle[0][0]); for (int i = 1; i < row; ++i) { pre = tmp[0]; tmp[0] += triangle[i][0]; for (int j = 1; j < tmp.size(); ++j) { int mid = tmp[j]; tmp[j] = min(pre, tmp[j]) + triangle[i][j]; pre = mid; } tmp.push_back(pre + triangle[i][triangle[i].size()-1]); } for (int i = 0; i < tmp.size(); ++i) { if (tmp[i] < ans) ans = tmp[i]; } return ans;}};
耗时一样。空间不一样。
leetcode Triangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。