记忆化搜索这名字听起来像是个高大上的算法概念，实际上你大概率早就见过它，只不过没往这个术语上想。刷过题的朋友应该对这类场景不陌生：明明写了个递归，逻辑也对，一提交就超时，加个数组把算过的结果存下来，瞬间从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[i+1][j] + dp[i][j+1]，只是填表时要注意从右下往左上填，因为这个转移依赖的是右边的格子和下边的格子。
这个转换过程我不建议死记硬背，最好的练习方式就是先把记忆化版本写对，再拿几道经典的 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]; }这里有个小细节，n=1 时返回 1，n=0 时也返回 1，是为了让 n=2 的时候 dfs(1)+dfs(0)=1+1=2，逻辑自洽。如果你把 n=0 写成返回 0，答案就错了。这种“出口值怎么定”的问题，在记忆化搜索里特别常见，一定要拿小数据手工验算一遍。
4.2 场景二：单词拆分
看一道稍微有难度的题，给定一个字符串 s 和一个单词字典 dict，问 s 能不能被拆分成若干个字典中出现的单词。比如 s = "leetcode"，dict 里有 "leet" 和 "code"，返回 true。
暴力递归的思路是：从下标 start 开始，尝试每一个可能的结尾 end，如果 s.substring(start, end) 在字典里，并且剩下的部分也能拆分，那就说明可行。用记忆化做：
boolean wordBreak(String s, List<String> wordDict) { Set<String> 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, Set<String> 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 当初始值，结果所有状态都没缓存住，复杂度直接回到指数级，本地测试 n=30 就卡死了，调试了半天才发现是初始值的问题。
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 你看一眼记忆化版本，思路立刻通透了。
最后分享一个我自己的习惯：遇到一道新题，我会先写暴力递归，再用小样例验证正确性，只有在递归超时之后才考虑加缓存。这个顺序看起来慢，实际上能帮你建立对问题结构的直觉——你能快速判断哪些子问题是重复的，哪些不是。等这个直觉养成了，再难的动态规划题在你眼里，也不过是一个递归加一张缓存表的事。
