C++

逆推

1 class Solution { 2 public: 3     /** 4      * @param triangle: a list of lists of integers. 5      * @return: An integer, minimum path sum. 6      */ 7     int minimumTotal(vector
     
      
        > &triangle) { 8         // write your code here 9         if (triangle.size() == 0)10             return 0;11             12         vector
       
         dp(triangle.size());13         14         dp[0] = triangle[0][0];15         for(int i = 1; i < triangle.size(); i++)16             for(int j = triangle[i].size() - 1; j >= 0; j--)17                 if (j == 0)18                     dp[j] = dp[j] + triangle[i][j];19                 else if (j == triangle[i].size() - 1)20                     dp[j] = dp[j-1] + triangle[i][j];21                 else22                     dp[j] = min(dp[j-1], dp[j]) + triangle[i][j];23                     24         int ret = INT_MAX;25         for(int i = 0; i < dp.size(); i++)26             ret = min(ret, dp[i]);27             28         return ret;  29     }30 };
       
      
     

 C++,修改原数组

1 class Solution { 2 public: 3     /** 4      * @param triangle: a list of lists of integers. 5      * @return: An integer, minimum path sum. 6      */ 7     int minimumTotal(vector
     
      
        > &triangle) { 8         // write your code here 9         for (int i = triangle.size() - 2; i >= 0; --i){10           for (int j = 0; j < i + 1; ++j){11             if(triangle[i+1][j] > triangle[i+1][j+1]){12               triangle[i][j] += triangle[i+1][j+1];13             }else{14               triangle[i][j] += triangle[i+1][j];15             }16           }17         }18         return triangle[0][0];19     }20 };