- class Solution {
- public:
- int minimumTotal(vector<vector<int>>& triangle) {
- if(triangle.size() == 1) return triangle[0][0];
- triangle[1][0] += triangle[0][0];triangle[1][1] += triangle[0][0];
- if(triangle.size() == 2) return min(triangle[1][0],triangle[1][1]);
- int a = min(triangle[1][0],triangle[1][1]);
- for(int i=0;i <2;i++){
- triangle[2][i] += a;
- }
- triangle[2][2] += triangle[1][1];
- for(int i=3;i < triangle.size();i++){
- triangle[i][0] += min(triangle[i-1][0],triangle[i-1][1]);
- for(int j=1;j < triangle[i].size()-2;j++){
- int x = min(triangle[i-1][j-1],triangle[i-1][j]);
- int y = min(x,triangle[i-1][j+1]);
- triangle[i][j] += y;
- }
- triangle[i][triangle[i].size()-2] += min(triangle[i-1][triangle[i].size()-2],triangle[i-1][triangle[i].size()-3]);
- triangle[i][triangle[i].size()-1] += triangle[i-1][triangle[i].size()-2];
- }
- return findmin(triangle[triangle.size()-1]);
- }
- int findmin(vector<int> temp){
- int minnum = temp[0];
- for(int i=1;i <temp.size();i++){
- if(minnum> temp[i]) minnum = temp[i];
- }
- return minnum;
- }
- };
-- 题意没写清楚, 相邻是左中右还是中右, WA 了一发
- class Solution {
- public:
- int minimumTotal(vector<vector<int>>& triangle) {
- if(triangle.size() == 1) return triangle[0][0];
- triangle[1][0] += triangle[0][0];triangle[1][1] += triangle[0][0];
- for(int i=2;i <triangle.size();i++){
- triangle[i][0] += triangle[i-1][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][triangle[i].size()-1] += triangle[i-1][triangle[i].size()-2];
- }
- return findmin(triangle[triangle.size()-1]);
- }
- int findmin(vector<int> temp){
- int minnum = temp[0];
- for(int i=1;i <temp.size();i++){
- if(minnum> temp[i]) minnum = temp[i];
- }
- return minnum;
- }
- };
- _
来源: http://www.bubuko.com/infodetail-2947321.html