Given an index k, return the kth 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?

Solution:

這題的思路是抓住上一行是如何轉(zhuǎn)化為下一行的：

1. 先在上一行的最左邊插入一個1
2. 然后在此時的上一行中除了頭尾兩個數(shù)之外，每個數(shù) [i] = [i] + [i + 1]，得到新的一行。

將Pascal's Triangle按如下形狀整理可更加直觀地表現(xiàn)以上思路：

    1
   11
  121
 1331
14641

code:

public class Solution 
{
    public List<Integer> getRow(int rowIndex) 
    {
        if(rowIndex < 0)
            return new ArrayList<>();
        
        List<Integer> row = new ArrayList<>();
        for(int i = 0; i <= rowIndex; i ++)
        {
            row.add(0, 1);
            
            //for (int j = 1; j < row.size() - 1; j ++)
            for(int j = 1; j < i; j ++)
                row.set(j, row.get(j) + row.get(j + 1));
        }
        return row;
    }
}