三角形最小路径和

传送门
递归爆搜超出时间限制，代码如下：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& t) {
       return dfs(t,0,0);
    }
    int dfs(vector<vector<int>>& t,int i,int j){
        if(i==t.size()) {return 0;}
        return min(dfs(t,i+1,j),dfs(t,i+1,j+1))+t[i][j];
    }
};

改为动态规划，从倒数第二行起，将该元素的最短路径覆盖在原来的位置，直到得出（0，0）位置的最短路径

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