【Python 算法零基础 3.递推】

压抑与痛苦，那些辗转反侧的夜，终会让我们更加强大

—— 25.5.16

一、递推的概念

递推 —— 递推最通俗的理解就是数列，递推和数列的关系就好比算法和数据结构的关系，数列有点像数据结构中的线性表(可以是顺序表，也可以是链表，一般情况下是顺序表)，而递推就是一个循环或者迭代的枚举过程，递推本质上是数学问题。

二、509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

方法一递归

① 终止条件

当 n == 0 时，直接返回 0（对应斐波那契数列的第 0 项）。

当 n == 1 时，直接返回 1（对应斐波那契数列的第 1 项）。

② 递归计算

当 n > 1 时，当前项的值为前两项之和：fib(n) = fib(n-1) + fib(n-2)。

递归调用自身计算 fib(n-1) 和 fib(n-2)，并返回它们的和。

    def fib(self, n: int) -> int:if n == 0:return 0elif n == 1:return 1else:return self.fib(n -2) + self.fib(n - 1)

方法二迭代

① 初始化结果列表

创建列表 res，初始值为 [0, 1]，对应斐波那契数列的前两项。

② 循环填充中间项

循环范围：i 从 2 到 n-1（不包含 n）。

递推公式：每次将 res[i-1] 和 res[i-2] 的和添加到 res 中。

返回结果：返回 res[n]，即列表的第 n 项（索引为 n）。

    def fib(self, n: int) -> int:res = [0, 1]for i in range(2, n + 1):res.append(res[i - 1] + res[i - 2])return res[n]

三、1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537

方法一递归

① 终止条件

当 n == 0 时，直接返回 0（对应斐波那契数列的第 0 项）。

当 n == 1 时，直接返回 1（对应斐波那契数列的第 1 项）。

当 n == 2 时，直接返回 1（对应斐波那契数列的第 2 项）。

② 递归计算

当 n > 1 时，当前项的值为前三项之和：fib(n) = fib(n-1) + fib(n-2) + fib(n-3)。

递归调用自身计算 fib(n-1) 和 fib(n-2)和fib(n-3)，并返回它们的和。

class Solution:def tribonacci(self, n: int) -> int:if n == 0:return 0elif n == 1 or n == 2:return 1else:return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)

方法二迭代

① 初始化结果列表

创建列表 res，初始值为 [0, 1, 1]，对应斐波那契数列的前三项。

② 循环填充中间项

循环范围：i 从 3 到 n + 1。

递推公式：每次将 res[i-1] 和 res[i-2] 和 res[i-3] 的和添加到 res 中。

返回结果：返回 res[n]，即列表的第 n 项（索引为 n）。

class Solution:def tribonacci(self, n: int) -> int:res = [0, 1, 1]for i in range(3, n + 1):res.append(res[i - 3] + res[i - 2] + res[i - 1])return res[n]

四、斐波那契数列变形爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

方法一递归

思路与算法

① 终止条件

当 n == 1 时，只有 1 种爬法（一步）。当 n == 2 时，有 2 种爬法（一步一步或直接两步）。

② 递归分解

当 n > 2 时，最后一步可能是从 n-1 级跨一步到达，或从 n-2 级跨两步到达。

因此，总爬法数为前两级的爬法数之和：climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)。

class Solution:def climbStairs(self, n: int) -> int:if n == 1:return 1elif n == 2:return 2else:return self.climbStairs(n - 1) + self.climbStairs(n - 2)

方法二迭代

思路与算法

① 初始化结果列表

创建列表 res，初始值为 [1, 1]，分别对应 n=0 和 n=1 的爬法数。注意：此处 res[0]=1 是为了后续计算方便，实际题目中 n ≥ 1，因此 res[0] 不会被直接使用。

② 循环填充结果列表

循环范围：i 从 2 到 n（包含 n）。

递推公式：对于每个 i，计算 res[i] = res[i-1] + res[i-2]，即前两级的爬法数之和。

返回结果：返回 res[n]，即第 n 级楼梯的爬法数。

class Solution:def climbStairs(self, n: int) -> int:res = [1, 1]for i in range(2, n + 1):res.append(res[i - 1] + res[i - 2])return res[n]

五、二维递推问题

像斐波那契数列这种问题，是一个一维数组来解决的，有时候一维数组解决不了的问题我们应该升高一个维度看

长度为 n(1 ≤ n < 40)的只由“A"、"C"、"M"三种字符组成的字符串，可以只有其中一种或两种字符，但绝对不能有其他字符，且禁止出现 M 相邻的情况，问这样的串有多少种？

思路与算法

① 边界条件处理

当 n = 0 时，直接返回 0（空字符串）。

② 状态定义

dp[i][0]：长度为 i 且最后一个字符是 M 的字符串数目。

dp[i][1]：长度为 i 且最后一个字符不是 M（即 A 或 C）的字符串数目。

Ⅰ、初始化

当 i = 1 时：dp[1][0] = 1（字符串为 M）。dp[1][1] = 2（字符串为 A 或 C）。

Ⅱ、状态转移（循环 `i` 从 2 到 `n`）

计算 dp[i][0]（末尾为 M）：前一个字符不能是 M（否则相邻），因此只能从 dp[i-1][1] 转移而来。递推式：dp[i][0] = dp[i-1][1]。

计算 dp[i][1]（末尾为非 M）：前一个字符可以是 M 或非 M（即 dp[i-1][0] + dp[i-1][1]）。当前字符有 2 种选择（A 或 C），因此总数乘以 2。递推式：dp[i][1] = (dp[i-1][0] + dp[i-1][1]) * 2。

Ⅲ、结果计算

最终结果为长度为 n 的所有合法字符串数目，即 dp[n][0] + dp[n][1]。

def count_valid_strings(n: int) -> int:if n == 0:return 0# dp[i][0]: 长度为i且最后一个字符是M的字符串数目# dp[i][1]: 长度为i且最后一个字符不是M的字符串数目dp = [[0, 0] for _ in range(n + 1)]dp[1][0] = 1  # Mdp[1][1] = 2  # A, Cfor i in range(2, n + 1):dp[i][0] = dp[i-1][1]  # 前一个字符不能是Mdp[i][1] = (dp[i-1][0] + dp[i-1][1]) * 2  # 前一个字符任意，当前选A/Creturn dp[n][0] + dp[n][1]

六、119. 杨辉三角 II

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

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

示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
提示:

0 <= rowIndex <= 33

进阶：

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

思路与算法

① 初始化结果列表

创建空列表 resRows，用于存储杨辉三角的每一行。

② 逐行生成杨辉三角

Ⅰ、外层循环（`i` 从 0 到 `rowIndex`）

对于每一行 i，创建空列表 resCols 用于存储当前行的元素。

Ⅱ、内层循环（`j` 从 0 到 `i`）：

边界条件：当 j 是当前行的第一个或最后一个元素时（即 j == 0 或 j == i），直接添加 1。

递推关系：否则，当前元素的值为上一行的 j-1 和 j 位置元素之和（即 resRows[i-1][j-1] + resRows[i-1][j]）。将当前行 resCols 添加到 resRows 中。

返回指定行：循环结束后，返回 resRows 中的第 rowIndex 行。

class Solution:def getRow(self, rowIndex: int) -> List[int]:resRows = []for i in range(rowIndex + 1):resCols = []for j in range(i + 1):if j == 0 or j == i:resCols.append(1)# f[i][j] = f[i - 1][j - 1] + f[i - 1][j]else:resCols.append(resRows[i - 1][j] + resRows[i - 1][j - 1])resRows.append(resCols)return resRows[rowIndex]

七、119. 杨辉三角 II 空间优化

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

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

示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
提示:

0 <= rowIndex <= 33

进阶：

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

算法与思路

① 初始化二维数组 `f`

创建一个 2 行、rowIndex+1 列的二维数组 f，用于存储中间结果。初始化 pre = 0 和 now = 1，分别表示当前行和前一行的索引。

② 设置初始条件

f[pre][0] = 1，对应杨辉三角的第一行 [1]。

③ 逐行生成杨辉三角

Ⅰ、外层循环（`i` 从 0 到 `rowIndex`）

遍历每一行，生成当前行的元素。

Ⅱ、内层循环（`j` 从 0 到 `i`）

边界条件：当 j 是当前行的第一个或最后一个元素时，设为 1。

递推关系：否则，当前元素的值为前一行的 j 和 j-1 位置元素之和（即 f[pre][j] + f[pre][j-1]）。更新 pre 和 now 的值，交换当前行和前一行的角色。

返回结果：循环结束后，pre 指向的行即为所求的第 rowIndex 行，返回 f[pre]。

class Solution:def getRow(self, rowIndex: int) -> List[int]:f = []for i in range(0, 2):l = []for j in range(rowIndex + 1):l.append(0)f.append(l)pre = 0now = 1f[pre][0] = 1for i in range(0, rowIndex + 1):l = []for j in range(i + 1):if j == 0 or j == i:f[now][j] = 1else:f[now][j] = f[pre][j] + f[pre][j - 1]pre, now = now, prereturn f[pre]