LeetCode 120. 三角形最小路径和

第一反应深搜，但是记忆化不太好整，还是一维dp逐层动归比较靠谱；

class Solution {
public:
    int minimumTotal(vector>& triangle) {
        int height=triangle.size();
        vectordp(height+1,0);
        dp[1]=triangle[0][0];
        for(int i=1;i
            vectortemp(height+1,0);
            for(int j=1;j<=i+1;j++){
                if(j==1){
                    temp[1]=dp[1]+triangle[i][0];
                    continue;
                }
                if(j==i+1){
                    temp[j]=dp[j-1]+triangle[i][j-1];
                    continue;
                }
                temp[j]=min(dp[j-1],dp[j])+triangle[i][j-1];
            }
            dp=temp;
        }
        int ret=INT_MAX;
        for(int i=1;i
            ret=min(ret,dp[i]);
        }
        return ret;
    }
};