## Wednesday, January 9, 2013

### [LeetCode] 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.
» Solve this problem

[解题思路]

[Code]

``````1:    int minimumTotal(vector<vector<int> > &triangle) {
2:      int row = triangle.size();
3:      if(row ==0) return 0;
4:      vector<int> minV(triangle[row-1].size());
5:      for(int i =row-1; i>=0; i--)
6:      {
7:        int col = triangle[i].size();
8:        for(int j =0; j<col; j++)
9:        {
10:          if(i == row-1)
11:          {
12:            minV[j] = triangle[i][j];
13:            continue;
14:          }
15:          minV[j] = min(minV[j], minV[j+1]) + triangle[i][j];
16:        }
17:      }
18:      return minV[0];
19:    }
``````