1. 从“暴力递归”到“记忆搜索”一个思维范式的转变很多刚接触算法的新手甚至一些有经验的开发者在面对“动态规划”这四个字时常常会感到一种莫名的压力。教科书和教程里充斥着各种“状态定义”、“状态转移方程”、“最优子结构”和“无后效性”的术语让人望而生畏。但如果你写过递归那么恭喜你你已经半只脚踏入了动态规划的大门。今天我们不谈那些晦涩的定义就从你最熟悉的递归开始聊聊如何通过一个简单的技巧——“记忆搜索”让那些原本慢到无法忍受的递归程序瞬间起飞并自然地过渡到标准的动态规划解法。我们将全程使用C来演示因为它的性能特性能让我们更直观地感受到优化前后的巨大差异。想象这样一个场景你要计算斐波那契数列的第n项。最直观的写法就是递归fib(n) fib(n-1) fib(n-2)基准条件是fib(1)fib(2)1。这个代码写起来非常优雅但当你尝试计算fib(50)时程序可能会陷入漫长的等待甚至因为递归栈过深或超时而崩溃。为什么因为其中存在大量的重复计算。fib(5)的计算需要fib(4)和fib(3)而fib(4)的计算又需要fib(3)和fib(2)…… 你会发现fib(3)被计算了无数次。这种指数级的时间复杂度是灾难性的。“记忆搜索”要解决的核心就是这个问题。它的本质不是一种全新的算法而是对递归算法的一种优化技术也被称为“自顶向下的动态规划”。思路直白得惊人既然重复计算是罪魁祸首那我们用一个数组或哈希表把已经计算过的结果存起来不就行了下次再遇到相同的参数时直接返回存储的结果避免重复的递归调用。这个存储用的数组就是我们常说的“记忆化数组”或“DP表”。从暴力递归到记忆搜索代码改动往往很小但效果是降维打击式的——时间复杂度通常能从指数级降低到多项式级。2. 斐波那契数列解剖第一个记忆化案例让我们用代码来具体感受一下这个转变。这是最经典的入门案例能清晰地展示问题所在和解决方案。2.1 暴力递归的代价我们先写出那个简洁但低效的版本#include iostream using namespace std; long long fib_naive(int n) { if (n 2) return 1; // 基准情况 return fib_naive(n - 1) fib_naive(n - 2); // 递归调用 } int main() { int n 45; // 尝试一个稍大的数 cout fib( n ) fib_naive(n) endl; return 0; }你可以试试运行计算fib(45)。在普通的机器上这可能需要好几秒甚至更长时间。如果我们画出递归树以计算fib(6)为例就会看到一棵庞大的、枝节蔓延的树其中fib(3)、fib(2)等节点重复出现了很多次。时间复杂度是 O(2^n)空间复杂度是 O(n)递归调用栈的深度。2.2 引入记忆化效率的飞跃现在我们引入一个全局的memo数组。这个数组的初始值可以设为 -1表示该位置的结果还未被计算。#include iostream #include vector using namespace std; vectorlong long memo; // 记忆化数组 long long fib_memo(int n) { // 1. 查表如果已经计算过直接返回结果 if (memo[n] ! -1) { return memo[n]; } // 2. 基准情况 if (n 2) { memo[n] 1; return 1; } // 3. 计算并存储递归计算但结果存入数组 memo[n] fib_memo(n - 1) fib_memo(n - 2); return memo[n]; } int main() { int n 45; memo.resize(n 1, -1); // 初始化大小为 n1所有值设为 -1 cout fib( n ) ) fib_memo(n) endl; return 0; }关键点解析memo数组的意义memo[i]存储的就是fib(i)的结果。它的存在使得每个fib(i)在完整的递归过程中只会被计算一次。“剪枝”操作if (memo[n] ! -1) return memo[n];这行代码是记忆搜索的灵魂。它像一个缓存系统命中缓存则直接返回避免了子树的重复展开。这相当于对递归树进行了“剪枝”。计算顺序注意我们并没有显式地定义先算谁后算谁。程序的计算顺序依然由递归调用fib_memo(n-1)和fib_memo(n-2)决定。但由于记忆化的存在整体上每个子问题只解决一次。运行这个版本计算fib(45)几乎是瞬间完成的。时间复杂度降低到了 O(n)因为每个fib(i)只计算一次空间复杂度为 O(n) 用于存储数组和递归栈。注意这里使用vectorlong long并初始化为 -1前提是结果不会是 -1。对于更通用的场景或者结果可能为任何值的情况可以使用一个单独的bool数组visited来标记是否已计算或者使用std::optional(C17) 或std::unordered_map。2.3 对比与思考它为什么是动态规划记忆搜索已经具备了动态规划的核心特征最优子结构fib(n)的最优解由fib(n-1)和fib(n-2)的最优解构成。重叠子问题这是被记忆化数组显式解决了的。状态这里的“状态”就是参数n表示计算斐波那契数列的第几项。状态转移memo[n] memo[n-1] memo[n-2]只不过这个转移是在递归返回过程中隐式完成的。它与教科书上常见的“自底向上”递推式动态规划如下所示在思路上是镜像的long long fib_dp(int n) { if (n 2) return 1; vectorlong long dp(n 1); dp[1] dp[2] 1; for (int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2]; // 显式的状态转移 } return dp[n]; }自底向上是“我从哪里来”从小问题开始逐步构建大问题的解。记忆搜索是“我到哪里去”从大问题出发遇到小问题就解决并记住。两者最终填满的是同一张DP表只是填表的顺序不同。记忆搜索更符合人类面对复杂问题时的自然思维分治而自底向上递推通常有更优的常数时间和空间优化潜力。3. 经典问题实战爬楼梯与零钱兑换理解了斐波那契我们来看两个更贴近实际、变化也更多的题目它们能更好地展示记忆搜索的威力。3.1 爬楼梯问题问题描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶这几乎就是斐波那契数列的变体。定义dfs(i)为爬到第i阶台阶的方法数。暴力递归dfs(i) dfs(i-1) dfs(i-2)基准是dfs(1)1,dfs(2)2。记忆化搜索直接套用模板。class Solution { public: int climbStairs(int n) { vectorint memo(n 1, -1); return dfs(n, memo); } private: int dfs(int i, vectorint memo) { if (i 2) return i; // 爬到第1阶1种方法第2阶2种方法 if (memo[i] ! -1) return memo[i]; memo[i] dfs(i - 1, memo) dfs(i - 2, memo); return memo[i]; } };这个实现清晰地将记忆化数组作为参数传递避免了全局变量。它完美地展示了如何将一个问题转化为“状态”当前台阶i和“选择”走1步或2步的模型。3.2 零钱兑换问题问题描述给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。这个问题比爬楼梯更进一步因为“选择”的数量不再固定硬币种类数并且要求的是“最小值”。第一步设计暴力递归函数我们定义dfs(target)函数表示凑出金额target所需的最少硬币数。基准情况如果target 0需要0枚硬币。如果target 0说明当前路径无效返回一个特殊值如INT_MAX或-1的某种表示。状态转移对于当前金额target我可以选择使用任意一枚面额小于等于target的硬币coins[i]。选择这枚硬币后问题就变成了一个子问题凑出金额target - coins[i]所需的最少硬币数。所以dfs(target) 1 min(dfs(target - coin))其中coin遍历所有有效的硬币。第二步加入记忆化递归过程中同一个target会被反复计算。例如硬币[1,2,5]凑11元dfs(9)可能会从11-2和11-1-1等多种路径到达。因此我们需要一个memo数组来存储dfs(target)的结果。class Solution { public: int coinChange(vectorint coins, int amount) { // memo[target] 表示凑出金额 target 的最少硬币数初始化为 -2 表示未计算 vectorint memo(amount 1, -2); return dfs(coins, amount, memo); } private: int dfs(const vectorint coins, int target, vectorint memo) { if (target 0) return -1; // 无效路径 if (target 0) return 0; // 凑齐了需要0枚硬币 // 查表 if (memo[target] ! -2) { return memo[target]; } int minCoins INT_MAX; for (int coin : coins) { int subResult dfs(coins, target - coin, memo); if (subResult 0) { // 子问题有解 minCoins min(minCoins, subResult 1); } } // 存储结果如果 minCoins 还是 INT_MAX说明所有选择都无解 memo[target] (minCoins INT_MAX) ? -1 : minCoins; return memo[target]; } };关键细节与踩坑点初始值的选择memo初始化为-2是为了区分“未计算”和“计算结果为 -1无解”。这是一个非常实用的技巧避免了误判。子问题无解的处理dfs返回-1表示无解。在汇总子问题结果时必须跳过无解的情况if (subResult 0)否则minCoins可能会被-110错误地更新。最终结果的存储循环结束后需要判断minCoins是否被更新过。如果没有即仍为INT_MAX则说明所有硬币选择都导致了无效路径当前target也无解应存储-1。这个例子充分说明了记忆搜索的通用性。只要你能写出正确的递归函数定义清楚状态和转移加上记忆化数组一个高效的动态规划解法就诞生了。它比直接思考递推公式要直观得多。4. 记忆搜索的局限性、技巧与优化虽然记忆搜索强大且直观但它并非银弹在实际使用中需要注意以下几点。4.1 递归深度限制递归调用会占用系统栈空间。对于问题规模n很大比如10^5的情况即使时间复杂度允许递归深度也可能导致栈溢出。例如在爬楼梯问题中如果递归树是一条单链理论上深度就是n。大多数评测系统和生产环境对栈深度都有限制。解决方案转换为递推这是最根本的解决方法。像斐波那契、爬楼梯问题可以很容易地改为for循环的递推形式彻底摆脱递归。尾递归优化某些编译器如GCC/Clang在较高优化等级下可以对特定形式的尾递归进行优化将其转换为循环但这不是C标准保证的且对递归函数写法有严格要求通用性不强。迭代加深搜索对于某些特定类型的问题如DFS这是一种策略但不适用于标准的记忆化DP。实操心得在算法竞赛或面试中如果问题规模明确可能很大优先考虑自底向上的递推DP。记忆搜索更适合作为思路推导的工具或者在确定递归深度可控时使用。4.2 状态设计与存储结构记忆化的核心是“状态”。如何设计一个能唯一标识子问题的“状态”是关键。一维状态如斐波那契、爬楼梯、零钱兑换仅金额直接用数组vectorT。高维状态很多问题需要多个参数才能定义子问题。例如经典的“背包问题”状态需要(i, j)表示考虑前i个物品在容量为j的背包下的最大价值。这时记忆化数组就需要是二维的vectorvectorT。复杂状态或稀疏状态当状态参数不是连续的整数或者范围非常大但实际用到的状态很少时使用数组可能浪费空间。这时可以用unordered_map哈希表来存储。例如状态是一个pairint, int或者一个自定义的结构体unordered_map是更好的选择尽管查询会有常数开销。// 使用哈希表进行记忆化的示例框架 unordered_maplong long, int memo; // key 通常需要编码成一个唯一值 int dfs(State state) { long long key encode(state); // 将状态编码为唯一key if (memo.count(key)) return memo[key]; // ... 计算过程 memo[key] result; return result; }4.3 记忆化与“无后效性”记忆化能工作的一个隐含前提是相同的状态参数无论通过何种路径到达其对应的最优解是唯一确定的。这就是动态规划的“无后效性”。如果你的问题不满足这个条件例如问题解依赖于到达当前状态的路径历史那么标准的记忆化/动态规划就可能失效可能需要增加状态维度来包含必要的历史信息。4.4 从记忆搜索到递推DP的思维桥梁我强烈建议将记忆搜索作为学习动态规划的第一步。它的步骤非常清晰定义递归函数明确函数签名dfs(state)和返回值意义。思考基准情况最简单、不可再分的情况直接返回结果。枚举所有选择在当前状态下列出所有可能的选择并递归调用dfs(next_state)。整合子问题结果根据题目要求求最大、最小、总数等合并子问题的结果得到当前状态的结果。加入记忆化添加一个存储结构在函数开头查表在返回前存表。当你熟练写出记忆搜索后要尝试着将其转化为递推DP这是一个重要的思维能力提升。观察记忆化数组的填充顺序。在记忆搜索中填表顺序是“需要什么才计算什么”是依赖驱动的。而递推DP需要你主动确定一个正确的计算顺序保证在计算dp[i]时它所依赖的所有子状态dp[...]都已经被计算出来。以零钱兑换为例记忆搜索是dfs(amount)调用dfs(amount-coin)。对应的递推DP就是int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, amount 1); // 初始化为一个最大值 dp[0] 0; // 基准情况 for (int i 1; i amount; i) { // 按金额从小到大计算 for (int coin : coins) { if (i - coin 0) { dp[i] min(dp[i], dp[i - coin] 1); } } } return dp[amount] amount ? -1 : dp[amount]; }这里for (int i 1; i amount; i)就是手动确定的计算顺序确保算dp[i]时所有dp[i - coin]都已经算好了。这个顺序恰好就是金额从小到大的自然顺序。5. 综合案例最长上升子序列LIS的记忆化解法最后我们用一个中等难度的问题来串联所有知识点最长上升子序列。给定一个整数数组nums找到其中最长严格递增子序列的长度。第一步设计递归回溯思路对于数组中的每个位置i我们考虑“以nums[i]作为上升子序列的最后一个元素”时能构成的最长长度dfs(i)。基准情况每个元素本身至少是一个长度为1的子序列。状态转移为了计算dfs(i)我们需要看所有在i之前的索引j(0 j i)。如果nums[j] nums[i]那么nums[i]可以接在以 nums[j] 结尾的子序列后面形成一个更长的子序列。所以dfs(i) max(dfs(j) 1)对所有满足nums[j] nums[i]的 j 取最大值。如果不存在这样的 j那么dfs(i) 1。第二步实现记忆化搜索这个递归存在大量重叠子问题。例如计算以不同位置i结尾的LIS时可能会反复计算以某个较早位置j结尾的LIS。class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint memo(n, -1); // memo[i] 存储 dfs(i) 的结果 int maxLen 1; // 计算以每个位置 i 结尾的 LIS 长度 for (int i 0; i n; i) { maxLen max(maxLen, dfs(nums, i, memo)); } return maxLen; } private: // 返回以 nums[pos] 结尾的最长上升子序列长度 int dfs(const vectorint nums, int pos, vectorint memo) { if (memo[pos] ! -1) return memo[pos]; int maxSubLen 1; // 至少包含自己长度为1 // 遍历 pos 之前的所有位置 for (int i 0; i pos; i) { if (nums[i] nums[pos]) { maxSubLen max(maxSubLen, dfs(nums, i, memo) 1); } } memo[pos] maxSubLen; return maxSubLen; } };第三步分析与转化这个解法的时间复杂度是 O(n²)因为每个dfs(i)要遍历所有j i而共有 n 个状态。空间复杂度是 O(n)。它已经比暴力回溯好太多了。观察这个记忆化搜索memo[i]依赖于所有memo[j](j i 且 nums[j] nums[i])。这提示我们递推的顺序就是按照索引i从 0 到 n-1 的顺序。我们可以轻松地写出等价的递推DPint lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint dp(n, 1); // dp[i] 表示以 nums[i] 结尾的 LIS 长度初始为1 int maxLen 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } maxLen max(maxLen, dp[i]); } return maxLen; }看递推的dp数组就是记忆化的memo数组两层循环明确地按照依赖关系填充了这张表。从记忆搜索到递推DP思维链路完全打通。记忆搜索不是动态规划的替代品而是理解动态规划的一把钥匙尤其适合解决状态转移不那么直观的复杂问题。它让你专注于问题本身的分解和组合而把优化交给“记忆”这个简单的机制。下次当你遇到一个看似复杂的动态规划问题时不妨先忘掉“状态转移方程”这个词试着问自己如果我用递归暴力解决函数应该怎么设计这个递归树里有哪些重复的子树想明白这些代码自然就水到渠成了。