📑 题目：119. 杨辉三角 II

简单 🕓 2021-04-27 📈 频次： 3

**

🚀 本题 LeetCode 传送门

题目大意

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

解题思路

• 题目中的三角是杨辉三角，每个数字是 (a+b)^n 二项式展开的系数。题目要求我们只能使用 O(k) 的空间。那么需要找到两两项直接的递推关系。由组合知识得知：

  [ egin{aligned}C{n}^{m} &= frac{n!}{m!(n-m)!} \C{n}^{m-1} &= frac{n!}{(m-1)!(n-m+1)!}end{aligned} ]

  于是得到递推公式：

  [ C{n}^{m} = C{n}^{m-1} imes frac{n-m+1}{m} ]

  利用这个递推公式即可以把空间复杂度优化到 O(k)

代码

package leetcode
func getRow(rowIndex int) []int {
 row := make([]int, rowIndex+1)
 row[0] = 1
 for i := 1; i <= rowIndex; i++ {
  row[i] = row[i-1] * (rowIndex - i + 1) / i
 }
 return row
}