Triangle

/*
Triangle
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.
*/
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
      if (triangle.size()==0) return 0;
      int nrow=triangle.size();
      for (int i=1; i<nrow; ++i)
      {
        for (int j=0; j<triangle[i].size(); ++j)
        {
          if (j==0) triangle[i][j] += triangle[i-1][0];
          else if (j==triangle[i].size()-1) triangle[i][j] += triangle[i-1][triangle[i-1].size()-1];
          else triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]);
        }
      }
      int minSum=INT_MAX;
      for (int i=0; i<triangle[nrow-1].size(); ++i)
      	if (triangle[nrow-1][i]<minSum) minSum=triangle[nrow-1][i];
      return minSum;
    }
};

REMARK:
1 Hard to do the problem using only O(n) extra space, where n is the total number of rows in the triangle. Have no idea.

Solution: No need to create extra space, we just use the 2-d array triangle[][] which already exist. Then this problem is similar to the problem Unique Paths, which is a dynamic programming problem using bottome-up way.

IDEA: Bottom-up dynamic programming. We change triangle[i][j] to the minimum sum at the position [i][j]. We build the new triangle[i][j] from the base case, i.e. the top of the triangle. Note: 
triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]) //general case
triangle[i][j] += triangle[i-1][0];//corner case
triangle[i][triangle[i-1].size()-1] += triangle[i-1][triangle[i-1].size()-1];//corner case
which can be seen through this index triangle:
      0
     0 1
    0 1 2
   0 1 2 3
  0 1 2 3 4