记忆化搜索详解：从暴力递归到动态规划的缓存优化实践

记忆化搜索这名字听起来像是个高大上的算法概念实际上你大概率早就见过它只不过没往这个术语上想。刷过题的朋友应该对这类场景不陌生明明写了个递归逻辑也对一提交就超时加个数组把算过的结果存下来瞬间从TLE变成AC。这个操作就是记忆化搜索。我的理解里记忆化搜索本质上是“带缓存的递归”。它解决的核心问题只有一个——同一个子问题被重复计算了无数次。在很多递归问题里如果直接暴力往下递归计算量会呈指数级爆炸但如果能把每次算出来的子问题结果缓存起来下次用到时直接取就能把指数级降成多项式级。这玩意儿听起来简单真正用好还是有讲究的尤其是和动态规划DP的关系、缓存怎么设计、边界条件怎么处理踩过坑的人才知道里面有多少细节。这篇文章我打算站在一个刷题老手的角度把记忆化搜索从原理到实操彻底聊透包括怎么从暴力递归一步步改成记忆化、和DP怎么互相转换、什么时候用记忆化比DP更合适最后再分享一些我实际调试中遇到的坑。内容会带不少代码Java为主但思路是通用的。1. 记忆化搜索的根为什么递归会超时1.1 一个看似人畜无害的递归先从一个最简单的例子说起斐波那契数列。教科书里都这么写递归int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }逻辑完美可是你拿 n 45 去跑一下能明显感觉到卡顿。n 50 基本就跑不完了。原因在于这个递归的调用树是指数级的fib(50) 会去算 fib(49) 和 fib(48)而 fib(49) 又要去算 fib(48) 和 fib(47)……注意fib(48) 被算了两次fib(47) 被算了三次越往下重复越多。我随手做个统计fib(30) 调用次数大概是 166 万次fib(40) 是 3.3 亿次左右。这个增长曲线非常恐怖根本扛不住。1.2 重复子问题是万恶之源用术语说上面这个递归里有大量的“重叠子问题”。什么意思就是同一个子问题在整个递归过程中会被反复求解而每次求解的路径一模一样结果也一模一样。重复造轮子不但浪费而且是超时的根本原因。这时记忆化就登场了既然 fib(48) 算一次就够了那我把它存到一个数组里下次再要的时候直接读数组复杂度瞬间从指数级降到了线性的 O(n)。思路就是这么朴素甚至没有一丁点的高深之处。但我得强调一个容易被忽略的点“能记忆化”是有前提的那就是子问题之间必须相互独立而且某个子问题一旦求出结果这个结果就是确定的、不随外界变化的。这就涉及到后面要说的“无后效性”了先埋个伏笔。2. 从暴力递归到记忆化两行代码的差距2.1 核心就三件事把暴力递归改成记忆化搜索本质上是三步搞一个缓存容器通常是数组或哈希表。递归函数一开始先查缓存有就直接返回。每次算出结果先存缓存再返回。拿斐波那契举例子改完就是这样的int fib(int n) { int[] memo new int[n 1]; Arrays.fill(memo, -1); return fibHelper(n, memo); } int fibHelper(int n, int[] memo) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; // 查缓存 memo[n] fibHelper(n - 1, memo) fibHelper(n - 2, memo); // 存缓存 return memo[n]; }核心就多了一个 if 判断和一次赋值。但要知道斐波那契这类问题用记忆化其实收益有限因为递归深度到 n而 n 通常有个上限。真正能体现记忆化巨大价值的是那种状态空间大、分支多的题目比如矩阵里的路径规划、字符串编辑距离、博弈类问题。2.2 二维场景里的记忆化以路径问题为例看一个更有代表性的例子机器人从左上角走到右下角只能往右或往下走路上有障碍物问有多少条不同路径。暴力递归写法是int uniquePaths(int[][] grid, int i, int j) { if (i grid.length || j grid[0].length || grid[i][j] 1) return 0; if (i grid.length - 1 j grid[0].length - 1) return 1; return uniquePaths(grid, i 1, j) uniquePaths(grid, i, j 1); }这个写法在小规模数据上没问题但一旦网格尺寸变成几十乘几十递归调用数就会爆炸。因为同一个 (i, j) 会被从不同路径反复访问到。加入记忆化之后int uniquePaths(int[][] grid, int i, int j, int[][] memo) { if (i grid.length || j grid[0].length || grid[i][j] 1) return 0; if (i grid.length - 1 j grid[0].length - 1) return 1; if (memo[i][j] ! -1) return memo[i][j]; memo[i][j] uniquePaths(grid, i 1, j, memo) uniquePaths(grid, i, j 1, memo); return memo[i][j]; }道理和斐波那契一脉相承区别只是缓存从一维数组变成了二维数组。但请注意这个例子里有个容易出错的点在于memo 数组初始值不能是 0因为合法的路径方案数本身就可能为 0如果初始值是 0 就没法区分“没算过”和“算出来是0”结果就会出错。我当年在这个坑上栽过后面常见问题部分专门说这个。3. 记忆化搜索和动态规划不是替代关系是同一个东西的两副面孔3.1 自顶向下与自底向上的视角差异很多人学 DP 的时候会困惑到底记忆化搜索是不是 DP我的结论是记忆化搜索就是 DP 的一种实现形式。动态规划的本质是“状态转移 状态缓存”记忆化搜索是自顶向下地递归然后缓存子问题的结果传统 DP 是自底向上地填表从最小的子问题开始逐步推到最终答案。我说个生活化的类比。你要算从一楼爬到十楼一共有多少种走法每一步可以跨一级或两级。记忆化搜索的思路是你想知道十楼就先想九楼和八楼再想九楼依赖的八楼和七楼……一路问到一楼二楼然后逐层把答案带回来但为了防止重复问你把每层答案都写在便利贴上贴在楼梯口。传统 DP 的思路是从一楼开始算把一楼的答案写好再算二楼再用一楼的答案去算三楼……一路填到十楼。殊途同归都是那几张便利贴只是一个从顶向下问一个从底往上算。3.2 什么时候记忆化比 DP 更顺手作为刷了几年题的老兵我个人的体感是某些场景下记忆化搜索写起来远比 DP 舒服。第一种场景是状态维度多、但实际访问到的状态很少。比如一个三维甚至四维的 DP如果用自底向上的填表法哪怕 80% 的状态根本用不到你也得把整个多维数组遍历一遍但记忆化搜索是“用到才算”递归只触达可达的状态常数上经常更优。第二种场景是状态转移方向不好确定。有些题目子问题之间的依赖关系太复杂自底向上很难找出一个清晰的填表顺序这时候自顶向下的递归天然就理顺了逻辑。最典型的就是博弈类问题比如“两个人从石子堆里取石子每次能取 1 或 2 个谁能赢”你写递归判断当前状态是必胜还是必败然后加个 memo代码结构非常直观。第三种场景是代码可读性和调试友好度。记忆化搜索的代码基本就是暴力递归加缓存逻辑和问题描述一一对应审查的时候一眼就能看出状态转移方程写没写对。相比之下自底向上的 DP 填充顺序一旦搞错排查起来真是头大。3.3 从记忆化到DP的转换心法虽说记忆化好用但有些场合你确实得转成 DP。比如某些在线评测系统对递归深度有限制n 上了 10 万直接栈溢出这时递归就废了必须改成迭代式 DP。转换的方法也有固定套路先写出记忆化搜索的递归函数弄清状态是什么、返回的是什么。把所有状态的维度列出来这基本就是 dp 数组的维度。找到递归的出口base case这对应 dp 数组的初始化。找到递归中“向下问”的依赖关系把它反向写成从底向上的递推关系。举个例子斐波那契的递归出口是 fib(0)0、fib(1)1转移是 fib(n)fib(n-1)fib(n-2)对应 DP 就是从 2 循环到 n。二维路径问题同理dp[i][j] dp[i1][j] dp[i][j1]只是填表时要注意从右下往左上填因为这个转移依赖的是右边的格子和下边的格子。这个转换过程我不建议死记硬背最好的练习方式就是先把记忆化版本写对再拿几道经典的 DP 题对比着做两遍慢慢就形成肌肉记忆了。4. 实操演示三个典型场景的完整拆解4.1 场景一爬楼梯问题先来一道最简单的热身题假设你正在爬楼梯需要 n 阶才能到顶每次可以爬 1 或 2 个台阶有多少种不同的方法爬到顶。递归思路很清晰到第 n 阶的方法等于到第 n-1 阶的方法加上到第 n-2 阶的方法这不就是斐波那契吗。但为了演示记忆化的完整流程我们仍然写一遍int climbStairs(int n) { int[] memo new int[n 1]; Arrays.fill(memo, -1); return dfs(n, memo); } int dfs(int n, int[] memo) { if (n 1) return 1; if (memo[n] ! -1) return memo[n]; memo[n] dfs(n - 1, memo) dfs(n - 2, memo); return memo[n]; }这里有个小细节n1 时返回 1n0 时也返回 1是为了让 n2 的时候 dfs(1)dfs(0)112逻辑自洽。如果你把 n0 写成返回 0答案就错了。这种“出口值怎么定”的问题在记忆化搜索里特别常见一定要拿小数据手工验算一遍。4.2 场景二单词拆分看一道稍微有难度的题给定一个字符串 s 和一个单词字典 dict问 s 能不能被拆分成若干个字典中出现的单词。比如 s leetcodedict 里有 leet 和 code返回 true。暴力递归的思路是从下标 start 开始尝试每一个可能的结尾 end如果 s.substring(start, end) 在字典里并且剩下的部分也能拆分那就说明可行。用记忆化做boolean wordBreak(String s, ListString wordDict) { SetString set new HashSet(wordDict); int[] memo new int[s.length()]; // 0未访问, 1可行, -1不可行 return dfs(s, 0, set, memo); } boolean dfs(String s, int start, SetString set, int[] memo) { if (start s.length()) return true; if (memo[start] ! 0) return memo[start] 1; for (int end start 1; end s.length(); end) { if (set.contains(s.substring(start, end)) dfs(s, end, set, memo)) { memo[start] 1; return true; } } memo[start] -1; return false; }这个例子里我用的 memo 就不是普通的 -1 初始化了而是 0 表示未访问1 表示可行-1 表示不可行。为什么不用 boolean因为 boolean 只有两个值没法区分“没访问过”和“访问过但是结果不可行”。这道题里有些子串从某个 start 出发就是拆分不了结果就是 false如果你用 boolean 数组默认 false那这个 false 到底是缓存结果还是没访问过根本分不清。这也是记忆化搜索里最经典的一个坑我后面会专门再展开。4.3 场景三区间DP型的记忆化像“戳气球”“矩阵连乘”“石子合并”这类区间 DP记忆化写起来特别顺手因为状态通常是 dp[i][j] 表示区间 [i, j] 上的最优解转移时枚举中间切分点 k。如果用自底向上的 DP你得小心处理区间长度的循环顺序但用记忆化直接递归 缓存就行代码非常贴近问题本身。拿石子合并举例求合并一堆石子需要的最小代价int mergeStones(int[] stones) { int n stones.length; int[] prefix new int[n 1]; for (int i 0; i n; i) prefix[i 1] prefix[i] stones[i]; int[][] memo new int[n][n]; for (int i 0; i n; i) Arrays.fill(memo[i], -1); return dfs(stones, prefix, memo, 0, n - 1); } int dfs(int[] stones, int[] prefix, int[][] memo, int i, int j) { if (i j) return 0; if (memo[i][j] ! -1) return memo[i][j]; int best Integer.MAX_VALUE; for (int k i; k j; k) { int cost dfs(stones, prefix, memo, i, k) dfs(stones, prefix, memo, k 1, j); best Math.min(best, cost); } int sum prefix[j 1] - prefix[i]; memo[i][j] best sum; return memo[i][j]; }这里用前缀和数组快速算区间和是区间 DP 的标配操作。状态数 O(n^2)每次转移枚举 k 是 O(n)总复杂度 O(n^3)。你要是能看懂这个例子区间 DP 基本就入门了。5. 缓存设计、状态设计与复杂度分析实操里最关键的三个环节5.1 缓存用什么容器、怎么初始化缓存容器取决于状态的维度。一维状态用数组二维状态用二维数组维度再多或者状态量稀疏就考虑用 Map 或者字符串拼接的 key。我个人的经验是状态是连续的整数下标优先数组访问快代码简洁。状态是离散的、稀疏的用 HashMap 更省空间。状态较多维时可以把多个维度打包成字符串当 key但别滥用字符串拼接本身有开销。缓存初始值必须是一个“不可能出现的合法结果”。如果你算的是方案数初始值用 -1如果你算的是布尔值初始值用 0 表示未访问1 和 -1 表示两种结果如果你算的是最大/最小值初始值用 Integer.MIN_VALUE 或 MAX_VALUE。这个规则看着简单实际写代码时很多人会踩。我自己最惨的一次是写一道方案数的题方案数结果可以是 0我用了 0 当初始值结果所有状态都没缓存住复杂度直接回到指数级本地测试 n30 就卡死了调试了半天才发现是初始值的问题。5.2 状态设计参数越少越好变化越少越好记忆化搜索的性能和正确性很大程度上取决于状态怎么定义。递归函数的每个可变参数基本就是状态的一个维度dp 数组的维度也跟着参数走。因此设计状态时有一个原则把“变化的量”压缩到最小。举个例子还是爬楼梯问题如果你写成 dfs(n, current) 表示从 current 到 n 有几种走法那状态就是二维的因为 current 在变、n 是个固定目标但你可能把它当参数传进去。实际上只需要一维状态 dfs(current) 就够了因为 n 在整个递归过程中是常量。把常量塞进状态里只会白白扩大缓存数组没有任何收益。反过来如果发现两个状态能合并成一个就不要分开。比如有些题目的状态是“位置 i”和“剩余步数 k”但实际到达位置 i 之后剩余步数也确定了那这两个参数可能本质是同一个状态的不同表现形式合并不了的时候就要认真分析转移。5.3 复杂度分析怎么看记忆化是不是白做了很多新手纠结一个问题加了缓存之后复杂度到底是多少我提供一个简单的估算方式状态数 × 每个状态转移的代价 总复杂度。状态数就是 memo 数组/表的有效大小转移代价就是递归函数内部除了递归调用之外做的常规操作比如循环枚举 k。拿石子合并的例子套一下状态数是 O(n^2)区间 i 和 j 的组合数每个状态需要枚举 k 做 O(n) 次操作总复杂度 O(n^3)。我还见过有的递归虽然加了缓存但每个状态内部还有一个嵌套循环总复杂度从 O(状态数×转移代价) 变成了 O(状态数×转移代价×某个因子)。这时候就要考虑能不能优化转移比如用前缀和、单调队列之类的技巧把转移代价降下来。缓存解决的是重复计算问题转移本身的开销是另一码事别搞混。6. 记忆化搜索进阶技巧与实战调试心得6.1 三个常踩的坑初始值、栈溢出、缓存污染先列一个我遇到过的坑清单方便大家自查初始值冲突缓存初始值等于某个合法结果值导致缓存失效。应对办法是拿样例数据手动推一遍或者干脆用“访问标记数组”单独记录状态是否算过。递归太深栈溢出记忆化搜索本质是递归递归深度等于状态转移链的长度。如果深度上万JVM 栈可能扛不住这时候要么转迭代 DP要么自己用栈模拟递归。我实际测试过Java 默认栈深大概在几千到一万上下具体看 JVM 参数和每次调用的栈帧大小。缓存没有正确区分“未访问”和“结果就是 0/负值”。这个上面反复强调了是记忆化搜索里最隐蔽的坑。6.2 工程实战中的记忆化不止刷题用得上记忆化搜索不只是算法竞赛的专属工具工程代码里同样有它的身影。举几个我实际写过的场景复杂业务规则的计算结果缓存。比如某个计费规则给定一堆参数算出最终价格参数组合有限但重复次数高就可以把计算结果缓存起来。图形学或数据可视化里的递归细分计算同样的节点会被多次访问缓存能大幅提升性能。编译器或解释器里的纯函数求值如果输入相同、结果必定相同就可以做 memoization。区别在于工程场景里的输入参数往往不是简单的整数下标可能是对象、字符串、组合键所以更常用的是 HashMap 或专门的缓存框架。思路完全一致相同的入参直接取缓存结果。6.3 一个调试技巧打印调用日志记忆化搜索写错了怎么排查我的做法是先在最开始时关掉缓存用暴力递归跑小数据和标准答案对拍再把缓存打开同样跑小数据看结果是否一致。如果暴力对了、记忆化错了那几乎可以断定是缓存逻辑的问题——要么初始值冲突要么某个状态的缓存被错误地复用了。必要时在递归入口打印参数和返回值但注意不要打印太多不然输出量会爆炸。关于缓存复用错误再说一个容易忽略的场景如果同一个 memo 数组被多组测试数据复用可能会导致上一次计算的结果污染这一次。比如你在一个循环里对多个字符串调用同一个记忆化函数如果 memo 数组没有按输入重置就可能读到上一次的旧缓存。解决的办法是每次调用前重置 memo或者把 memo 作为局部变量传入。6.4 记忆化搜索的“未来方向”状态压缩与空间优化进阶玩家可能还会遇到状态压缩的问题。有些题目状态维度多直接开多维数组内存不够就得把多个状态编码成一个整数。比如二进制的状态压缩 DP本质上也可以理解成记忆化搜索加状态压缩只是缓存的下标变成了一个位掩码整数。位运算能压缩状态表示但不能压缩状态数该算的复杂度还是得算。还有空间优化的思路比如斐波那契其实不需要开一整个数组只需要保存前两个值滚动更新。记忆化搜索中如果发现某个状态只依赖它前面的少数几个状态可以考虑用滚动缓存但一般只有转成迭代 DP 后才更适合这么干。7. 一个小抄记忆化搜索的通用模板说了这么多我把平时写记忆化搜索的逻辑总结成一个模板大家可以照着套改一改就能用在大多数题目上// 假设状态由参数 a, b 决定返回值类型为 T T solve(params) { // 1. 定义缓存容器维度与状态参数一致 T[][] memo ...; // 2. 初始化为“不可能出现的值” // 3. 调用递归入口 return dfs(a, b, memo); } T dfs(params, memo) { // 1. 递归出口base case // 2. 查缓存命中直接返回 // 3. 枚举所有可能的选择递归计算子问题 // 4. 汇总结果存入缓存 // 5. 返回结果 }只要你写递归的时候能理清楚三件事——base case 是什么、状态用什么参数表示、子问题怎么从当前问题拆分——记忆化基本就是水到渠成的事。框架本身不难难的是分析出正确的状态转移而这恰恰需要多做几道题培养手感。说到底记忆化搜索的核心价值和难点从来都不在于“加缓存”这三个字而在于你是否能准确地定义“子问题”。子问题定义好了状态转移自然就顺了缓存只是锦上添花。这也是为什么我总觉得与其背各种 DP 套路不如先老老实实把记忆化搜索练扎实很多 DP 你看一眼记忆化版本思路立刻通透了。最后分享一个我自己的习惯遇到一道新题我会先写暴力递归再用小样例验证正确性只有在递归超时之后才考虑加缓存。这个顺序看起来慢实际上能帮你建立对问题结构的直觉——你能快速判断哪些子问题是重复的哪些不是。等这个直觉养成了再难的动态规划题在你眼里也不过是一个递归加一张缓存表的事。