题解 | 三角形最小路径和

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型vector<vector<>> 
     * @return int整型
     */
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        //自顶向下遍历，最上面一行即i=0,直到第n行i=n-1时得到答案
        int n=triangle.size();
        if(n==0) return 0;
        vector<vector<int>> dp(n,vector(n,0));
        dp[0][0]=triangle[0][0];
        for(int i=1;i<n;i++){
            for(int j=0;j<=i;j++){
                if(j==0) dp[i][j]=dp[i-1][j]+triangle[i][j];//j==0时，只有从上面走下来
                else if(i==j) dp[i][j]=dp[i-1][j-1]+triangle[i][j];//i==j时，只有从（i-1,j-1）处走下来
                else dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j];//一般情况，包括两种可能
            }
        }
        int res=dp[n-1][0];
        for(int i=1;i<n;i++){
            res=min(res,dp[n-1][i]);
        }
        return res;
    }
};