首页 > 其他 > 详细

【Leetcode】120.Triangle

时间:2016-10-12 06:50:24      阅读:189      评论:0      收藏:0      [点我收藏+]

[Question]

 

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).

 

[Solution]

//C++

class Solution {
public:
    int minimumTotal(vector& triangle) {
        if(triangle.size()==0)
            return 0;

        if(triangle.size()==1)
            return(triangle[0][0]);

        for(int i=triangle.size()-2; i>=0; i--){
            for(int j=0; j<=i; j++){
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};               

 

【Leetcode】120.Triangle

原文:http://www.cnblogs.com/liez/p/5951358.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!