leetcode120. 三角形最小路径和

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

优化

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