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

Given an index k, return the k^th 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]为该三角形第i行，第j列的元素，所以可以获得递推函数为

   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

滚动数组实现。注意Line11，要从后往前加，否则会产生冗余计算。

[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:    }