leetcode 120. 三角形最小路径和_henujolly的博客-爱代码爱编程

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