给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[     [2],    [3,4],   [6,5,7],  [4,1,8,3]]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

空间复杂度o(0)

1 class Solution {2 public:3     int minimumTotal(vector
     
      
       >& triangle) {4         for (int i = triangle.size() - 2; i >= 0; i--)5             for (int j = 0; j < triangle[i].size(); j++)6                 triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);7         return triangle[0][0];8     }9 };
      
     

空间复杂度o(n)

1 class Solution { 2 public: 3     int minimumTotal(vector
     
      
       >& triangle) { 4         int n = triangle.size(); 5         int m = triangle[0].size(); 6         if(n == 0 && m == 0) 7         { 8             return 0; 9         }10         vector
       
         dp = triangle[n - 1];11         for(int i = n - 2;i >= 0;i--)12         {13             m = triangle[i].size();14             for(int j = 0;j < m;j++)15             {16                 dp[j] = min(dp[j],dp[j+1]) + triangle[i][j];17             }18         }19         return dp[0];20     }21 };