## Friday, December 28, 2012

### [LeetCode] Pascal's Triangle II 解题报告

Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return `[1,3,3,1]`.

```[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]```
Note:
Could you optimize your algorithm to use only O(k) extra space?
» Solve this problem

[解题报告]

`[`
` [1],`
` [1,1],`
` [1,2,1],`
` [1,3,3,1],`
` [1,4,6,4,1]`
`]`

T[i][j] = T[i-1][j] + T[i-1][j-1] if i>0 && j>0
Or
=  1  if i=0
Or
=  T[i-1][j]  if j=0

[Code]
``````1:    vector<int> getRow(int rowIndex) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      vector<int> result;
5:      result.resize(rowIndex+2);
6:      for(int i =0; i< rowIndex+2; i++)
7:        result[i] = 0;
8:      result[1]=1;
9:      for(int i =0; i< rowIndex; i++)
10:      {
11:        for(int j =rowIndex+1; j>0; j--)
12:        {
13:          result[j] = result[j-1] + result[j];
14:        }
15:      }
16:      result.erase(result.begin());
17:      return result;
18:    }
``````