119. 杨辉三角 II

Difficulty
easy
Tags
动态规划
URL
https://leetcode-cn.com/problems/pascals-triangle-ii/
Star
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
notion imagenotion image
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
提示:
  • 0 <= rowIndex <= 33
进阶：
你可以优化你的算法到 O(rowIndex) 空间复杂度吗？

法1 动态规划

思路
同上一题
🪘
118. 杨辉三角 只不过本题只维护上一层和当前层
题解
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]

        pre = [[1]]
        for i in range(1, rowIndex+1):
            cur = [1]
            for j in range(0, i-1):
                cur.append(pre[j]+pre[j+1])
            cur.append(1)
            pre = cur[:]
        return cur

法2 组合数

思路
本题还有一种思路：组合数。
第i行第j个元素表示从i个数字中取j个数字有几种取法。比如下图的4，在第4行第1列，那他表示从4个数字中取1个数字有4种取法。
notion imagenotion image
有了这样的认知，我们就可以直接填充某一行了。
💡
Python计算组合数的内置函数 from math import comb
题解
from math import comb
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]

        res = [1] * (rowIndex+1)
        for i in range(1, rowIndex):
            res[i] = comb(rowIndex, i)

        return res
当然，我们也可以自己写计算组合数的函数
class Solution:
    
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]
        self.memo = [[None]*(rowIndex+1) for _ in range(rowIndex+1)]

        res = [1] * (rowIndex+1)
        for i in range(1, rowIndex):
            res[i] = self.nCk(rowIndex, i)

        return res 
		
			# 组合数计算方法
			# nCk: n个nums中choice k个num
    def nCk(self, n, k):
        if k == 0 or k == n:
            return 1

        if self.memo[n][k] is None:
            self.memo[n][k] = self.nCk(n-1, k-1) + self.nCk(n-1, k)

        return self.memo[n][k]
理解：在个数字中选取个数，那么有两种情况：
  • 选择当前数字，等价于在个数字中选个
  • 不选择当前数字，等价于在个数字中选个