算法分析与设计►未分类

triangle

解题思路


前一行的节点到达下一行的某个节点（记为v）的代价是一样的，故而到达v时的最小消耗将由前一行可到达v值的两个节点的最小值决定。

假设共有V个点。

时间复杂度 空间复杂度
O(V) O(1)

Code

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int res=0;
        for(int i=1;i<triangle.size();i++){
            for(int j=0;j<triangle[i].size();j++){
                if(j==0){
                    triangle[i][j]+=triangle[i-1][j];
                }
                else if(j==triangle[i].size()-1){
                    triangle[i][j]+=triangle[i-1][j-1];
                }
                else{
                    int mini;
                    if(triangle[i-1][j]>triangle[i-1][j-1])
                        mini=triangle[i-1][j-1];
                    else
                        mini=triangle[i-1][j];
                    triangle[i][j]+=mini;
                }
            }
        }
    res=triangle[triangle.size()-1][0];
    for(int i=1;i<triangle[triangle.size()-1].size();i++){

        res=min(res,triangle[triangle.size()-1][i]);
    }
    return res;
    }
};

运行结果

triangle