EEPW论坛

Given an index k, return the k th row of the Pascal's triangle.

For example, given k = 3,
Return[1,3,3,1].

Note: 

Could you optimize your algorithm to use only O(k) extra space?

题意：输出指定行的帕斯卡三角形的值；并且要求空间负责度为o(k)；因此采用的方法是只使用一个定长的数组，用于存储每一行的元素值，对于每个新的行，可对原先存放的行从后往前扫描，主要分为以下三种情况；

最后一个元素，直接等于1、对于下标为i的中间元素，有result[i]=result[i-1]+result[i];

最后一个元素，直接等于1；

1. class Solution  

2. {  

3. public:  

4.     vector<int> getRow(int rowIndex)  

5.     {  

6.         vector<int> result(rowIndex+1, 0);  

7.         result[0] = 1;  

8.   

9.         for (int i=1; i<rowIndex+1; i++)  

10.         {  

11.             for (int j=i; j>=1; j--)  

12.             {  

13.                 result[j] += result[j-1];  

14.             }  

15.         }  

16.   

17.         return result;  

18.     }  

19. };