本文共 1315 字，大约阅读时间需要 4 分钟。

#define INF 0x6FFFFFFFclass Solution {public:    int minimumTotal(vector
   
    
      > &triangle) {        // Start typing your C/C++ solution below        // DO NOT write int main() function		if(triangle.size() == 0)			return 0;		int n = triangle.size();        vector
     
      
       > dp(n+1);		for(int i = 0; i <= n; ++i)			dp[i].assign(n+1, INF);		//init value		dp[1][1] = triangle[0][0];		for(int i = 2; i <= n; ++i)		{			for(int j = 1; j <= i; ++j)			{				dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])+triangle[i-1][j-1];			}		}		//output		int ans = INF;		for(int j = 1; j <= n; ++j)			ans = min(dp[n][j], ans);		return ans;    }};
      
     
    
   

second time

class Solution {public:    int minimumTotal(vector
   
    
      > &triangle) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        int n = triangle.size();        if(n == 0) return 0;        vector
     
       f(n+1, INT_MAX);        for(int m = 1; m <= n; ++m)        {            for(int j = m; j >= 1; --j)            {                if(m == 1 && j == 1) f[j] = triangle[m-1][j-1];                else f[j] = min(f[j], f[j-1])+triangle[m-1][j-1];            }        }                int mmin = INT_MAX;        for(int j = 1; j <= n; ++j) mmin = min(f[j], mmin);                return mmin;    }};
     
    
   

转载地址：http://bhxti.baihongyu.com/