题目

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

image.png

示例:

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

方案一（递归+cache）

import functools

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        return [self.f(rowIndex, j) for j in range(rowIndex + 1)]

    @functools.lru_cache(maxsize=None)
    def f(self, i, j) -> int:
        # f(i, j) = f(i - 1, j - 1) + f(i - 1, j)
        if j == 0 or i == j:
            return 1
        return self.f(i - 1, j - 1) + self.f(i - 1, j)

原文

https://leetcode-cn.com/explore/featured/card/recursion-i/257/recurrence-relation/1203/