# 递推方程实战：从斐波那契数列到算法竞赛题解（附Python代码） 很多刚开始接触算法竞赛或者想深入理解动态规划的朋友，都会在“递推方程”这个概念上卡壳。教科书和理论文章往往从特征方程、齐次非齐次这些抽象术语开始，推导过程严谨但总让人觉得离实际敲代码解决问题有段距离。我自己最初备赛时也这样，看着一堆数学符号头疼，直到在几道经典题目里反复摔打，才突然意识到：**递推方程的本质，就是用一个清晰的数学式子，把“大问题如何拆成小问题”这个核心思路固定下来**。它不是什么高深的数学魔法，而是你设计算法时的“设计图纸”。 这篇文章，我想完全从实战和编码的角度，和你聊聊递推方程。我们会绕过最枯燥的纯理论证明，直接看几个最经典的例子——从人尽皆知的斐波那契数列，到算法竞赛中常见的爬楼梯、零钱兑换问题。我会用Python代码，把建立方程、求解、优化的每一步都掰开揉碎。你会发现，那些听起来唬人的“特征根”“特解形式”，在具体的题目背景下，都有非常直观的理解方式和应对技巧。我们的目标很明确：**让你看完就能动手，在下次遇到类似问题时，能自己写出正确的递推关系，并高效地用代码实现它。** ## 1. 热身：从斐波那契数列理解递推思想 斐波那契数列大概是所有人递归思维的启蒙。它的定义简单得不能再简单： > F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (当 n >= 2) 这个 `F(n) = F(n-1) + F(n-2)` 就是一个最经典的**常系数线性齐次递推方程**。说人话就是：当前项的值，完全由它前面固定几项（这里是两项）的线性组合（直接相加）决定，并且没有额外的“外力”项。 我们先写一个最直接的递归实现，这也是理解递推关系最自然的翻译： ```python def fib_naive(n): """朴素递归解法：直观但效率极低""" if n <= 1: return n return fib_naive(n-1) + fib_naive(n-2) # 测试小规模数据 print(f"F(5) = {fib_naive(5)}") # 输出 5 print(f"F(10) = {fib_naive(10)}") # 输出 55 ``` 运行一下 `fib_naive(30)` 你可能就要等上一会儿了。为什么呢？因为它的递归树是指数级爆炸的。这就引出了递推关系求解的第一个实战要点：**直接递归翻译往往不是最优解，我们需要更高效的求解方法。** 对于斐波那契数列这种**齐次线性递推**，理论上可以用特征根法求出通项公式。它的特征方程是： ``` x^2 = x + 1 -> x^2 - x - 1 = 0 ``` 解得特征根：`x1 = (1 + √5)/2 ≈ 1.618`, `x2 = (1 - √5)/2 ≈ -0.618`。 于是通解为 `F(n) = A * x1^n + B * x2^n`，代入初始条件 F(0)=0, F(1)=1 可以解出 A 和 B，最终得到著名的比内公式。但在编程竞赛中，我们很少真的去计算这个包含无理数的公式，因为浮点数精度可能出问题。更实用的方法是下面这两种： **1. 带备忘录的递归（自顶向下）** ```python from functools import lru_cache @lru_cache(maxsize=None) def fib_memo(n): """使用缓存装饰器，避免重复计算""" if n <= 1: return n return fib_memo(n-1) + fib_memo(n-2) ``` `@lru_cache` 是 Python 3.2+ 的神器，它自动帮你存储已计算的结果，将时间复杂度从 O(2^n) 降到了 O(n)。 **2. 迭代动态规划（自底向上）** ```python def fib_dp(n): """迭代动态规划，空间可优化""" if n <= 1: return n prev, curr = 0, 1 # 分别代表 F(i-1) 和 F(i) for i in range(2, n + 1): prev, curr = curr, prev + curr # 状态转移 return curr ``` 这种方法只用了常数空间，是竞赛中最常见的写法。它本质上就是在**正向地、迭代地求解递推方程**。 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | | :--- | :--- | :--- | :--- | | 朴素递归 | O(2^n) | O(n) | 仅用于理解，绝不用于实际计算 | | 记忆化递归 | O(n) | O(n) | 递归思路清晰，且状态依赖树状时 | | 迭代DP | O(n) | O(1) | 绝大多数线性递推的最优解 | 从斐波那契这个简单例子，我们提炼出处理递推方程的通用思路：**定义状态 -> 写出状态转移方程（递推式）-> 确定初始条件 -> 选择高效的计算方式（递归/迭代/公式）。** 接下来，我们看一个稍微复杂点的“变种”。 ## 2. 状态扩展：爬楼梯问题的多种递推建模 爬楼梯问题描述如下：你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？ 这本质上还是斐波那契数列。设 `dp[i]` 为爬到第 i 阶的方法数。要到达第 i 阶，你只能从第 i-1 阶爬1步上来，或者从第 i-2 阶爬2步上来。所以递推方程依然是： ``` dp[i] = dp[i-1] + dp[i-2] ``` 初始条件：`dp[0] = 1` (理解为站在地面有一种方式), `dp[1] = 1`。 但如果条件变化一下，问题就更有趣了。假设每次可以爬 1、2 或 3 个台阶呢？递推方程很容易推广： ``` dp[i] = dp[i-1] + dp[i-2] + dp[i-3] ``` 初始条件需要 `dp[0]=1, dp[1]=1, dp[2]=2`。 我们再增加一点难度，这也是竞赛中常见的变形：**每次爬的台阶数不是一个固定集合，而是一个数组 `steps`，例如 `[1, 3, 5]`，表示每次只能爬1、3或5阶。** 这时递推方程需要遍历所有可能的“上一步”： ```python def climb_stairs_general(n, steps): """ 通用爬楼梯问题 :param n: 楼梯总阶数 :param steps: 列表，每次可爬的阶数 :return: 爬到第n阶的不同方法数 """ dp = [0] * (n + 1) dp[0] = 1 # 初始状态 for i in range(1, n + 1): for step in steps: if i - step >= 0: dp[i] += dp[i - step] # 核心递推 return dp[n] # 测试：每次可爬1、3、5阶，爬到第7阶有多少种方法？ steps = [1, 3, 5] print(f"爬到第7阶的方法数: {climb_stairs_general(7, steps)}") ``` 这个递推关系 `dp[i] = sum(dp[i-step] for step in steps if i-step >= 0)` 依然是一个**线性递推**，但系数不再是固定的1，而是由 `steps` 数组决定。它对应的齐次递推方程特征根求解会复杂很多，不过在实际编程中，我们根本不需要去求特征根，直接用动态规划迭代求解即可。 > **提示**：当递推关系中的“步长”集合变大时，直接迭代的时间复杂度是 O(n * m)，其中 m 是步长种类数。如果 n 很大（例如 10^5），而步长集合也很大，可能需要用更高级的数据结构（如前缀和）来优化求和过程。 从爬楼梯问题，我们学会了如何根据规则变化来调整递推方程。这比死记硬背公式重要得多。接下来，我们进入一个更核心的领域：当递推方程不再是简单的“求和”，而是包含了“最值”或“选择”时，该如何建模。 ## 3. 从线性到非线性：零钱兑换与最优子结构 零钱兑换问题是动态规划的另一个经典入门题：给你一个整数数组 `coins` 表示不同面额的硬币，以及一个整数 `amount` 表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果无法凑成，返回 -1。 这个问题和爬楼梯在形式上很像，但有一个关键区别：**求的是最小值，而不是总和**。这导致它的递推方程不再是线性的，但依然具有最优子结构。 定义状态 `dp[i]` 为凑出金额 `i` 所需的最少硬币数。思考：要凑出金额 `i`，我们可以最后使用一枚面额为 `coin` 的硬币，那么剩下的金额就是 `i - coin`，而凑出 `i - coin` 的最少硬币数就是 `dp[i-coin]`。我们只需要遍历所有可能的 `coin`，选择那个使得 `dp[i-coin] + 1` 最小的方案。 于是得到递推方程： ``` dp[i] = min( dp[i - coin] + 1 ) for coin in coins if i - coin >= 0 ``` 初始条件：`dp[0] = 0`（凑出0元需要0个硬币），其他 `dp[i]` 初始化为一个很大的数（比如 `amount + 1` 或 `float('inf')`），表示暂时不可达。 Python实现如下： ```python def coin_change(coins, amount): """零钱兑换：求凑成金额所需的最少硬币数""" # 初始化dp数组，dp[i]表示金额i的最小硬币数 dp = [float('inf')] * (amount + 1) dp[0] = 0 # 边界条件 for i in range(1, amount + 1): for coin in coins: if i - coin >= 0: # 状态转移：选择使用这枚硬币，并更新最小值 dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 # 测试 coins = [1, 2, 5] amount = 11 print(f"凑出{amount}元最少需要 {coin_change(coins, amount)} 枚硬币") # 输出 3 (5+5+1) ``` 这个递推方程 `dp[i] = min(...)` 是一个**非齐次**的吗？从严格的数学定义看，它甚至不是常系数的线性递推，因为 `min` 操作不是线性运算。但在算法领域，我们仍然宽泛地称之为“递推关系”或“状态转移方程”。它的求解不依赖于特征根理论，而是依赖于动态规划的填表法。 为了加深理解，我们对比一下爬楼梯（计数型）和零钱兑换（最值型）的异同： | 方面 | 爬楼梯（计数） | 零钱兑换（最值） | | :--- | :--- | :--- | | **问题核心** | 求到达终点的**总方法数** | 求到达终点的**最小代价** | | **递推操作** | 求和 (`sum`) | 取最小值 (`min`) | | **初始值** | `dp[0] = 1` (一种方法) | `dp[0] = 0` (零代价) | | **不可达状态** | 通常为0（没有方法） | 通常为无穷大 (`inf`) | | **数学性质** | 线性齐次递推 | 非线性递推（但满足最优子结构） | > **注意**：零钱兑换的硬币无限使用，这保证了每个 `dp[i]` 只依赖于更小的 `i`，构成了一个“无后效性”的递推序列。如果硬币数量有限，就变成了背包问题，状态需要增加一维来表示使用情况，递推关系也会更复杂。 掌握了最值型递推，我们来看一个更刺激的：递推关系中带有“选择”和“条件判断”，这在字符串和序列处理中非常常见。 ## 4. 复杂依赖与边界处理：最长递增子序列（LIS） 最长递增子序列是面试和竞赛中的常客。给定一个整数数组 `nums`，找到其中最长严格递增子序列的长度。 例如，`nums = [10, 9, 2, 5, 3, 7, 101, 18]`，最长递增子序列是 `[2, 5, 7, 101]` 或 `[2, 5, 7, 18]`，长度是4。 这个问题的递推关系设计，比前几个例子更需要技巧。我们定义 `dp[i]` 为：**以第 i 个数字结尾的最长递增子序列的长度**。注意这个定义，它把状态固定在了“以 i 结尾”，这样我们才能方便地利用历史状态。 思考：对于位置 `i`，要想让 `nums[i]` 接在某个子序列后面形成更长的递增子序列，前提是 `nums[j] < nums[i]`（其中 `j < i`）。所以，我们需要检查所有在 `i` 之前的 `j`，如果 `nums[j] < nums[i]`，那么 `dp[i]` 就有可能更新为 `dp[j] + 1`。我们要取所有可能情况中的最大值。 递推方程如下： ``` dp[i] = max( dp[j] + 1 ) for j in range(i) if nums[j] < nums[i] ``` 初始条件：每个位置至少可以以自己开头，所以 `dp[i] = 1`（对于所有 i）。 Python代码实现： ```python def length_of_lis(nums): """最长递增子序列 - 标准动态规划解法 O(n^2)""" if not nums: return 0 n = len(nums) dp = [1] * n # 初始化，每个元素自身至少是一个长度为1的子序列 max_length = 1 for i in range(n): # 遍历 i 之前的所有位置 j for j in range(i): if nums[j] < nums[i]: # 如果 nums[j] 小于 nums[i]，则可以接在后面形成更长的子序列 dp[i] = max(dp[i], dp[j] + 1) # 更新全局最大值 max_length = max(max_length, dp[i]) return max_length # 测试 nums = [10, 9, 2, 5, 3, 7, 101, 18] print(f"最长递增子序列长度: {length_of_lis(nums)}") # 输出 4 ``` 这个递推关系 `dp[i] = max(...)` 同样是非线性的，并且带有一个条件判断 `if nums[j] < nums[i]`。它无法用简单的特征方程求解，必须通过动态规划迭代计算。这里也引出了一个重要的优化点：上述解法时间复杂度是 O(n^2)。对于 n 较大时（比如 10^4），可能会超时。竞赛中通常会用贪心+二分查找将其优化到 O(n log n)，但那又是另一个话题了。 LIS 问题展示了递推关系中**多对一依赖**和**条件转移**的典型模式。处理这类问题的关键是： 1. **精准定义状态**（通常以某个位置结尾）。 2. **枚举所有可能的前驱状态**（`j < i`）。 3. **在满足条件的前提下进行状态转移**（`nums[j] < nums[i]`）。 我们最后来看一个更综合、更接近竞赛难题的例子，它涉及状态机思想和多维状态设计。 ## 5. 综合实战：股票买卖系列中的状态机递推 股票买卖问题是动态规划中状态机模型的绝佳范例。我们以“买卖股票的最佳时机 IV”（限定最多完成 k 笔交易）为例，看看如何建立精妙的递推方程组。 问题：给定一个整数数组 `prices` 表示股票每天的价格，以及一个整数 `k`，表示你最多可以完成 k 笔交易（买一次卖一次算一笔）。你不能同时参与多笔交易，必须在再次购买前出售掉之前的股票。求你能获得的最大利润。 这个问题的状态比之前复杂得多。一天结束时，你可能有以下几种情况： - 持有 0 支股票，且今天没有进行卖出操作（可能是从未买过，或是之前卖出了）。 - 持有 1 支股票（可能是今天买的，或是之前买的还没卖）。 - 而且，我们还需要记录已经完成了几笔交易（买卖算一笔）。 因此，我们需要一个二维甚至三维的状态数组。一个经典且高效的状态定义是： - `dp[i][j][0]`：在第 i 天结束时，最多进行了 j 笔交易，且**当前不持有股票**的最大利润。 - `dp[i][j][1]`：在第 i 天结束时，最多进行了 j 笔交易，且**当前持有股票**的最大利润。 有了状态定义，递推方程就可以根据每天的操作（买入、卖出、休息）来推导： 1. `dp[i][j][0]` （今天结束时没股票）：可能昨天也没股票，今天休息；或者昨天有股票，今天卖了（完成一笔交易）。 ``` dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]) ``` 2. `dp[i][j][1]` （今天结束时持有股票）：可能昨天就有股票，今天休息；或者昨天没股票，今天买了（注意，买入操作会开启一笔新交易，所以交易次数上限 j 要对应）。 ``` dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) ``` 初始条件需要仔细考虑： - 第0天，还没开始，对于任何 j >= 0： - `dp[0][j][0] = 0` （没股票，利润为0） - `dp[0][j][1] = -prices[0]` （如果一开始就买入股票，利润为负的股价） - 对于 j = 0（不允许交易）： - `dp[i][0][0] = 0` （不允许交易，不持有股票，利润始终为0） - `dp[i][0][1] = -inf` （不允许交易，不可能持有股票，用负无穷表示不可能状态） 最终答案就是 `dp[n-1][k][0]`，即最后一天，最多完成 k 笔交易，且不持有股票的最大利润。 Python实现（进行了空间优化，将三维数组压缩为二维）： ```python def max_profit_k_transactions(k, prices): """买卖股票的最佳时机 IV：最多k笔交易""" n = len(prices) if n == 0 or k == 0: return 0 # 如果k很大，相当于无限次交易，可以用贪心简化 if k >= n // 2: # 贪心法：只要第二天比今天贵就交易 max_profit = 0 for i in range(1, n): if prices[i] > prices[i-1]: max_profit += prices[i] - prices[i-1] return max_profit # 动态规划：dp[j][0] 表示最多j次交易，不持有股票；dp[j][1] 表示最多j次交易，持有股票 # 初始化第一天的状态 dp = [[0, -prices[0]] for _ in range(k + 1)] # 注意：dp[0][1] 应该是不可能状态，但这里初始化为 -prices[0] 不影响后续递推，因为 j 从1开始遍历 for i in range(1, n): # 注意：需要倒序遍历交易次数，避免使用今天更新过的值 for j in range(k, 0, -1): # 今天不持有股票 = max(昨天就不持有, 昨天持有今天卖出) dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]) # 今天持有股票 = max(昨天就持有, 昨天不持有（且交易次数少一次）今天买入) dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]) return dp[k][0] # 测试 prices = [3, 2, 6, 5, 0, 3] k = 2 print(f"最多进行{k}笔交易的最大利润: {max_profit_k_transactions(k, prices)}") # 输出应为 7 (2买6卖, 0买3卖) ``` 这个例子里的递推关系是一个**状态机模型**，它由两个（或多个）相互关联的递推方程组成，共同描述了系统（你的持仓和交易状态）随时间（天数）的演变。这种模型在解决复杂决策问题时非常强大。 从斐波那契的简单线性叠加，到爬楼梯的规则扩展，再到零钱兑换的最值选择、LIS的条件转移，最后到股票买卖的状态机，递推方程的形式越来越复杂，但其核心思想一以贯之：**定义清晰的状态，找出状态之间如何转移，然后从初始状态开始，一步步推导出最终答案。** 理论上的特征根、齐次非齐次分类，为我们理解线性递推的通解形式提供了数学基础，但在实际编程解题中，我们更多依赖的是这种“状态转移”的思维和高效的迭代实现。下次当你面对一个看似复杂的问题时，不妨先问自己：它的“状态”是什么？这些状态之间是如何“递推”的？想清楚了这两个问题，代码往往就水到渠成了。