Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

 

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