简单

问题描述

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

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

示例 1:

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

示例 2:

输入: rowIndex = 0
输出: [1]

示例 3:

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

提示:

• 0 <= rowIndex <= 33

进阶：你可以优化你的算法到 O(rowIndex) 空间复杂度吗？

动态规划

假设层数为 $i$，那么第 $i$ 层就有 $i$ 个元素，且首尾是 $1$，假设 $dp[i][j]$ 表示第 $i$ 层，第 $j$ 个数，那么对于 $i > 0$， $0 < j < i$ 就有： $dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$，根据上一行的结果计算出当前行的结果即可，可以使用滚动数组的思想优化空间，利用背包的思想，还能降到只使用一维数组。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$。

数学

杨辉三角第 $n$ 行的 $m$ 个数可表示为 $C_{n-1}^{m-1}$，即为从 $n-1$ 个不同元素中取 $m-1$ 个元素的组合数。

由组合公式 $C_{n}^{m} = \dfrac{n!}{m!(n-m)!}$ 可以推导出同一行的相邻组合数的关系为：

$$C_{n}^{m} = C_{n}^{m-1} \times \dfrac{n-m+1}{m}$$

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
  const ans = new Array(rowIndex + 1).fill(1)
  for (let i = 1; i < rowIndex; i++) {
    ans[i] = (ans[i - 1] * (rowIndex - i + 1)) / i
  }
  return ans
}

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。