题解 | #三角形最小路径和#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型vector<vector<>> 
     * @return int整型
     */
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        int n=triangle.size();
        //纯递归会超时
        //因为当前层值只能来源于下层相邻位置，所以当前位置依赖取决于 当前trianglei[i][j]加上dp[i+1][j]或者dp[i+1][j+1]的值谁更小
        int dp[n][n];
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<triangle[i].size();j++){
                if(i==n-1){
                    dp[i][j]=triangle[i][j];
                }else{
                    dp[i][j]=min(triangle[i][j]+dp[i+1][j],
                    dp[i+1][j+1]+triangle[i][j]);
                }
            }
        }
        return  dp[0][0];
    }
};