题目链接

题目描述

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

示例

示例1：

输入: rowIndex = 3 输出: [1,3,3,1]

提示

• 0 <= rowIndex <= 33

  思路

  思路1：递推

  直接使用0118-杨辉三角的方法，不过我们可以对其进行优化：ans[i] 只与前一项 ans[i-1] 有关，因此可以倒推计算，这样保证了计算 ans[i] 时 ans[i-1] 仍是上一行的值。

  思路2：组合数

  由组合数公式，得到递推公式
  由此我们可以将时间优化到线性。
  ps.在Python3.8新增函数math.comb(n, k)，可以计算组合数。

  题解

  思路1：递推

  class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        ans = [0 for i in range(0, rowIndex + 1)]
        ans[0] = 1
        for i in range(1, rowIndex + 1):
            for j in range(i, 0, -1):
                ans[j] = ans[j] + ans[j - 1]
        return ans

  思路2：组合数

  ```python class Solution: def getRow(self, rowIndex: int) -> List[int]:

    ans = [0 for i in range(0, rowIndex + 1)]
    ans[0] = 1
    for i in range(1, rowIndex + 1):
        ans[i] = ans[i - 1] * (rowIndex - i + 1) // i
    return ans

库函数版

from math import comb class Solution: def getRow(self, rowIndex: int) -> List[int]: ans = [0 for i in range(0, rowIndex + 1)] for i in range(0, rowIndex + 1): ans[i] = comb(rowIndex, i)

    return ans

```

复杂度分析

思路1：递推

• 时间复杂度：

• 空间复杂度：

  思路2：组合数

• 时间复杂度：

• 空间复杂度：