题目

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

1 2	输入: 3 输出: [1,3,3,1]

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

1 2	Input: 3 Output: [1,3,3,1]

Follow up:

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

解题方法

杨辉三角第i行特征：一共i项，且分别为：

$C_i^0、C_i^1、Ci^2…C_i^{i-2}、C_i^{i-1}、C_i^i$

，即第一项为0；由组合数公式：

$C_a^b=\frac{a!}{(a-b)!b!}$

，可以得出它具有这样的特征：

$C_a^b=\frac{C_a^{b-1}*(a-b+1)}{b}$

根据上面两个特征很容易求出杨辉三角的第K行。这段代码跑了1ms，超过了97.72%的Java提交。

public class Solution {
  	// Method 2 1ms 97.72%
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        long cur = 1;
        res.add((int) cur);
        for (int i = 1; i <= rowIndex; i++) {
            cur = cur*(rowIndex - i + 1) / i;
            res.add((int) cur);
        }
        return res;
    }
}