三角形最小路径和

---

image.png

暴力：

class Solution {
public:
    int minnum=INT_MAX;
    void DFS(vector<vector<int>>& triangle,int x,int y,int value){
        if(x>=triangle.size()){
            minnum=min(minnum,value);
            return;
        }
        DFS(triangle,x+1,y,value+triangle[x][y]);
        DFS(triangle,x+1,y+1,value+triangle[x][y+1]);
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        for(int i=0;i<triangle[0].size();i++){
            DFS(triangle,1,i,triangle[0][i]);
        }
        return minnum;
    }
};

DP：

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