[LeetCode]120.Triangle

正午 2020-01-14 PM 10℃ 0条

给定一个三角形,找到从最上层到最下层的最小和路径
例子 输入下面的三角形

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

输出为:2 + 3 + 5 + 1 = 11 第一行取 2 第二行取 3 第三行取 5 第四行取 1。

解法一:
从最后一层往上计算

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        
        int n = triangle.size();
        for(int r = n-1; r>0; r--){
            for(int i=0; i<r; i++){
                triangle[r-1][i] += min(triangle[r][i], triangle[r][i+1]);
            }
        }
        return triangle[0][0];
        
    }
};
标签: LeetCode

非特殊说明,本博所有文章均为博主原创。

评论