思路 动态规划问题就是找函数表达式，本题的函数表达式就是 f[i][j]代表第i行第j列的数字到三角形低端的最短距离 f[i][j]=min(f[i+1][j],f[i+1][j+1])+triangle[i][j];
代码
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n=triangle.size(); if(n==0) return 0; if(n==1) return triangle[0][0]; vector <vector<int> > dp(n,vector <int> (n,0)); for(int i=0;i<n;i++) { dp[n-1][i]=triangle[n-1][i]; } for(int i=n-2;i>=0;i--) { for(int j=0;j<=i;j++) { dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]; } } return dp[0][0]; } };