1. 项目概述：从递归到搜索的算法实战之旅

如果你正在学习C++算法，或者刷题时总感觉递归和搜索是两道难以逾越的坎，那么这篇文章就是为你准备的。我见过太多初学者，一看到Fibonacci数列的递归解法就头疼，更别提复杂的深度优先搜索问题了。但我想告诉你，从最简单的Fibonacci到看似复杂的DFS，中间有一条清晰、可循的路径。这条路径的核心，就是理解递归的本质，并学会用“记忆化”这把利器，将暴力搜索从指数级的时间复杂度中拯救出来。今天，我们就以C++为工具，手把手走完这条路。你会发现，无论是蓝桥杯的真题，还是面试中的经典问题，其内核都离不开我们今天要讲的这几个核心思想。这篇文章不仅会给你代码，更会给你一套思考问题和优化代码的“肌肉记忆”。

2. 算法核心：递归、搜索与记忆化的三位一体

要打通从Fibonacci到DFS的任督二脉，我们必须先理解三个核心概念：递归、深度优先搜索和记忆化。它们不是孤立的，而是一个层层递进、相互支撑的体系。

2.1 递归：算法世界的“俄罗斯套娃”

递归，简单说就是函数自己调用自己。它把一个大规模问题，分解成一个或几个规模更小的、但形式完全相同的子问题，直到子问题小到可以直接求解。Fibonacci数列的定义F(n) = F(n-1) + F(n-2)就是递归的完美体现：要知道F(n)，你得先知道F(n-1)和F(n-2)。

递归代码写起来非常优雅，符合人类的直觉思维。但它的致命伤是效率。以最朴素的Fibonacci递归实现为例，计算F(5)的过程就像一棵疯狂生长的二叉树：

F(5) / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) / \ F(2) F(1)

你会发现，F(3)被计算了2次，F(2)被计算了3次。当n增大到40或50时，这棵树的节点数（即函数调用次数）将接近2^n，这是一个天文数字，程序会陷入漫长的等待甚至直接崩溃。这就是所谓的“重叠子问题”——同一个子问题被反复计算多次。识别出“重叠子问题”，是我们进行优化的第一步。

2.2 深度优先搜索：一条道走到黑的探索者

深度优先搜索是一种用于遍历或搜索树、图结构的算法。它的策略如其名：尽可能深地搜索图的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

在算法题中，DFS通常以递归的形式实现。比如在一个迷宫中找路，从起点开始，选择一个方向走下去，直到走到死胡同，再退回上一个岔路口选择另一个方向。这种“尝试-回溯”的机制，天然适合用递归来表达。递归函数中的每一层调用，都对应着搜索树中的一层，而函数调用栈则自动帮我们记录了“回溯点”。

2.3 记忆化搜索：给递归加上“备忘录”

记忆化搜索是解决上述“重叠子问题”的银弹。它的思想极其朴素：既然同一个子问题会被计算多次，那我何不第一次算出来的时候就把结果记下来？下次再遇到，直接查表返回，省去重复计算。

这个“备忘录”通常是一个数组（DP数组）或哈希表（如unordered_map），其下标或键与递归函数的参数一一对应。在递归函数开始时，先检查备忘录里是否有当前参数对应的结果，有则直接返回；没有，则正常计算，并在返回前将结果存入备忘录。

记忆化搜索不是一种独立的算法，而是递归和动态规划之间的桥梁。它保留了递归的直观性，又拥有了动态规划的高效性。可以说，带记忆化的递归，就是自顶向下的动态规划。理解这一点，对你后续学习更复杂的动态规划问题至关重要。

3. 从Fibonacci出发：理解记忆化的第一块敲门砖

让我们用代码来直观感受记忆化的魔力。我们将实现三个版本的Fibonacci数列求解，并对比它们的性能。

3.1 朴素递归：优雅但低效的起点

#include <iostream> using namespace std; using ll = long long; const ll MOD = 1e9 + 7; ll fib_naive(int n) { if (n <= 2) return 1; return (fib_naive(n - 1) + fib_naive(n - 2)) % MOD; } int main() { int n = 50; // 试试看50 // clock_t start = clock(); cout << fib_naive(n) << endl; // clock_t end = clock(); // cout << "Time: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl; return 0; }

这段代码简洁明了，但当n=50时，在我的测试机上需要近一分钟才能算出结果。你可以取消注释计时代码感受一下。问题就在于之前分析的指数级重复计算。

3.2 记忆化递归：效率的飞跃

现在我们引入一个dp数组作为备忘录。

#include <iostream> #include <cstring> using namespace std; using ll = long long; const ll MOD = 1e9 + 7; const int MAX_N = 10000; ll dp[MAX_N + 5]; // 备忘录，dp[i]记录F(i)的值 ll fib_memo(int n) { if (n <= 2) return 1; // 关键检查：如果已经计算过，直接返回存储的结果 if (dp[n] != -1) return dp[n]; // 否则，计算并存储结果 dp[n] = (fib_memo(n - 1) + fib_memo(n - 2)) % MOD; return dp[n]; } int main() { int n = 10000; // 现在可以轻松计算到10000 memset(dp, -1, sizeof(dp)); // 初始化为-1，表示未计算 // 初始化基础情况 dp[1] = dp[2] = 1; cout << fib_memo(n) << endl; return 0; }

核心要点解析：

1. dp数组初始化：我们使用memset(dp, -1, sizeof(dp))将数组初始化为-1。这里选择-1是因为Fibonacci数列的值都是正数，-1可以作为一个安全的“未计算”标志。你也可以用-1或0（如果0不是有效结果）。
2. 检查备忘录：在递归函数开头，if (dp[n] != -1) return dp[n];这行代码是记忆化的灵魂。它拦截了所有重复的计算请求。
3. 存储结果：在计算完结果后，dp[n] = ...将结果保存起来。注意，这里我们直接修改了dp[n]，然后返回它。也可以写成return dp[n] = (fib_memo(n-1) + fib_memo(n-2)) % MOD;，更加简洁。

经过记忆化优化后，每个F(i)只会被计算一次，时间复杂度从恐怖的O(2^n)降到了O(n)。计算F(10000)也只是一瞬间的事情。

3.3 迭代法：另一种视角

作为补充，我们再看一下自底向上的迭代法，也就是标准的动态规划写法：

ll fib_iter(int n) { if (n <= 2) return 1; ll a = 1, b = 1, c; for (int i = 3; i <= n; ++i) { c = (a + b) % MOD; a = b; b = c; } return b; }

这种方法同样高效，且只使用了常数空间。它和记忆化递归是等价的，只是思考方向不同：一个从顶向下分解，一个从底向上构建。

实操心得：在面试或竞赛中，如果问题有明显的递推关系且n很大，优先考虑迭代法，它通常常数更小，且没有递归栈溢出的风险。但记忆化递归在思维上更直观，尤其是对于状态定义复杂的问题。

4. 记忆化搜索实战：破解“混境之地”迷宫问题

掌握了Fibonacci的记忆化，我们来看一个更贴近实际算法题的案例。假设有一个n x m的网格迷宫，每个格子有高度h[i][j]。你从起点(ix, iy)出发，只能走到相邻（上下左右）且高度严格低于当前格子的格子。此外，你有一个“背包”道具，可以使用一次，使用后下一次移动可以走到高度低于当前格子高度+k的格子。问能否到达终点(ex, ey)。

4.1 问题分析与状态定义

这是一个典型的路径存在性问题。没有背包时，移动规则是h[nx][ny] < h[x][y]。使用背包后，当次移动规则变为h[nx][ny] < h[x][y] + k，且使用后背包状态改变。

关键洞察：这个问题的状态不仅取决于当前位置(x, y)，还取决于背包是否已经使用过（t）。因为从同一个点出发，带着背包和没带背包，能走的路径是完全不同的。因此，我们的状态应该是一个三元组：(x, y, t)。其中t=0表示背包未使用，t=1表示已使用。

记忆化数组dp[x][y][t]就用来记录：从状态(x, y, t)出发，能否到达终点。它的值可以是-1（未计算），0（不能到达），1（可以到达）。

4.2 暴力DFS实现与瓶颈

我们先写出最直观的暴力DFS版本，理解搜索过程：

bool dfs(int x, int y, int t) { if (x == ex && y == ey) return true; // 到达终点 // 向四个方向尝试 int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 越界检查 if (t == 0) { // 背包未使用 // 选择1：不用背包，正常移动 if (h[nx][ny] < h[x][y] && dfs(nx, ny, 0)) return true; // 选择2：使用背包，进行跳跃 if (h[nx][ny] < h[x][y] + k && dfs(nx, ny, 1)) return true; } else { // 背包已使用 // 只能正常移动 if (h[nx][ny] < h[x][y] && dfs(nx, ny, 1)) return true; } } return false; // 四个方向都走不通 }

这个版本逻辑清晰，但效率极低。考虑一个所有格子高度都相同且无法使用背包的迷宫，DFS会尝试所有可能的路径，其复杂度在最坏情况下可达O(4^(n*m))，因为每个点有最多4个方向可走。

4.3 引入记忆化：化指数为多项式

现在我们加入记忆化数组dp。

#include <iostream> #include <cstring> using namespace std; const int N = 1005; int h[N][N]; int dp[N][N][2]; // -1:未计算，0:false，1:true int n, m, k, ix, iy, ex, ey; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; bool dfs(int x, int y, int t) { if (x == ex && y == ey) return true; // 记忆化检查：如果状态已计算，直接返回 if (dp[x][y][t] != -1) return dp[x][y][t]; bool canReach = false; for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; if (t == 0) { if (h[nx][ny] < h[x][y] && dfs(nx, ny, 0)) canReach = true; if (!canReach && h[nx][ny] < h[x][y] + k && dfs(nx, ny, 1)) canReach = true; // 短路优化 } else { if (h[nx][ny] < h[x][y] && dfs(nx, ny, 1)) canReach = true; } if (canReach) break; // 找到一个能到达的路径即可提前结束 } // 存储结果：将bool转换为int存储 dp[x][y][t] = canReach ? 1 : 0; return canReach; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); memset(dp, -1, sizeof(dp)); cin >> n >> m >> k; cin >> ix >> iy >> ex >> ey; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> h[i][j]; cout << (dfs(ix, iy, 0) ? "Yes" : "No") << endl; return 0; }

代码精讲与避坑指南：

1. 状态存储：dp[x][y][t]存储的是从(x,y,t)出发的最终结果（能否到终点）。一旦计算出结果，无论后续搜索如何调用到这个状态，都直接返回，避免了以该状态为起点的所有子搜索的重复计算。
2. 初始化：memset(dp, -1, sizeof(dp))将所有状态标记为“未计算”。注意memset按字节赋值，-1的二进制表示是0xFF，对于int类型来说，四个字节都是0xFF，其值仍然是-1，这是安全的。
3. 返回值处理：在递归函数中，我们用一个局部变量canReach记录本层搜索的结果，最后统一存入dp数组并返回。这样逻辑更清晰，也便于调试。
4. 短路优化：在t==0的分支里，如果不用背包已经能到达(canReach为真)，就没必要再尝试用背包的路径了。这是一个小小的优化，在某些情况下能减少递归调用。

经过记忆化后，每个状态(x, y, t)最多只被计算一次。总状态数是n * m * 2，每个状态需要尝试最多4个方向，因此时间复杂度优化到了O(n * m)，这是一个质的飞跃。

注意事项：记忆化搜索有效的前提是，在相同的输入状态下，函数的输出结果是确定且唯一的。在这个问题中，给定起点、背包状态和固定的迷宫，结果就是唯一确定的。如果问题中存在“随机性”或“后效性”（当前决策影响之前的状态），则不能直接使用记忆化。

5. 高阶应用：记忆化搜索解决“地宫取宝”计数问题

我们来看一个更复杂的例子，它来自蓝桥杯真题。问题可以抽象为：在一个n x m的网格中，每个格子有宝物价值c[i][j]。你从左上角(1,1)出发，只能向右或向下走，走到右下角(n,m)结束。沿途你可以拿宝物，但必须满足：1. 当前要拿的宝物价值必须严格大于手中已有宝物的最大价值；2. 最终手中的宝物数量恰好为k。求不同的行动方案总数，结果对1e9+7取模。

5.1 状态设计与暴力DFS

这个问题不再是简单的“能否到达”，而是要求“方案数”。因此，我们的DFS函数应该返回一个数值（方案数），而不是布尔值。

状态设计：当我们走到(x, y)时，能影响后续决策的因素有哪些？

1. 当前位置(x, y)。
2. 当前手中宝物的最大价值max_val。这决定了下一个宝物能不能拿。
3. 当前手中宝物的数量cnt。这决定了我们还能拿多少宝物，以及最终是否满足条件。

因此，状态可以定义为(x, y, max_val, cnt)。DFS函数dfs(x, y, max_val, cnt)的含义是：从(x,y)出发，手中宝物最大价值为max_val，数量为cnt，走到终点且最终宝物数恰好为k的方案数。

暴力DFS框架：

ll dfs(int x, int y, int max_val, int cnt) { // 到达终点 if (x == n && y == m) { return (cnt == k) ? 1 : 0; } ll res = 0; // 只能向右或向下走 int dx[] = {1, 0}; int dy[] = {0, 1}; for (int i = 0; i < 2; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx > n || ny > m) continue; // 越界 // 情况1：拿当前格子的宝物（如果可以拿） if (c[nx][ny] > max_val && cnt < k) { res = (res + dfs(nx, ny, c[nx][ny], cnt + 1)) % MOD; } // 情况2：不拿当前格子的宝物 res = (res + dfs(nx, ny, max_val, cnt)) % MOD; } return res; } // 初始调用：从(1,1)开始，有两种选择：拿或不拿第一个宝物 ll ans = (dfs(1, 1, 0, 0) + dfs(1, 1, c[1][1], 1)) % MOD;

一个关键陷阱：注意，“拿”和“不拿”是两种独立的选择，不是互斥的。只要满足拿的条件（价值更大且未拿满），我们就可以选择拿；同时，无论能否拿，我们总是可以选择不拿。因此，这两个res = (res + dfs(...))是顺序执行、累加的关系，绝对不能写成if...else。写成else就变成了“能拿就必须拿，不能拿才不拿”，这完全错误，会漏掉大量“能拿但选择不拿”的合法方案。

5.2 引入记忆化与细节处理

暴力DFS的复杂度是指数级的，必须记忆化。我们的记忆化数组dp需要能覆盖所有状态。

#include <iostream> #include <cstring> using namespace std; using ll = long long; const int N = 55; // 注意：题目规模n,m<=50，数组开55足够 const ll MOD = 1e9 + 7; int c[N][N]; int n, m, k; ll dp[N][N][14][14]; // dp[x][y][max_val][cnt] ll dfs(int x, int y, int max_val, int cnt) { // 记忆化检查 if (dp[x][y][max_val][cnt] != -1) return dp[x][y][max_val][cnt]; if (x == n && y == m) { // 到达终点，只有宝物数量刚好为k才算一种方案 return dp[x][y][max_val][cnt] = (cnt == k) ? 1 : 0; } ll res = 0; // 方向：右、下 if (y + 1 <= m) { // 向右走 int nx = x, ny = y + 1; // 拿 if (c[nx][ny] > max_val && cnt < k) { res = (res + dfs(nx, ny, c[nx][ny], cnt + 1)) % MOD; } // 不拿 res = (res + dfs(nx, ny, max_val, cnt)) % MOD; } if (x + 1 <= n) { // 向下走 int nx = x + 1, ny = y; // 拿 if (c[nx][ny] > max_val && cnt < k) { res = (res + dfs(nx, ny, c[nx][ny], cnt + 1)) % MOD; } // 不拿 res = (res + dfs(nx, ny, max_val, cnt)) % MOD; } return dp[x][y][max_val][cnt] = res; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); memset(dp, -1, sizeof(dp)); cin >> n >> m >> k; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> c[i][j]; c[i][j]++; // 关键操作！价值统一+1 } } // 初始状态：在(1,1)处，可以选择拿或不拿 ll ans = (dfs(1, 1, 0, 0) + dfs(1, 1, c[1][1], 1)) % MOD; cout << ans << endl; return 0; }

几个至关重要的细节：

1. 数组大小：dp[N][N][14][14]。为什么第三、四维是14？因为k的最大值是12（题目给定），而max_val是宝物价值。题目说宝物价值在[0, 12]之间。但我们做了c[i][j]++操作，将价值映射到了[1, 13]。所以max_val的范围是0（表示还没拿任何宝物）到13，共14种可能。cnt的范围是0到12（k最大值），共13种，但开到14更安全。这里如果开成dp[N][N][13][13]，当max_val=13或cnt=12时会数组越界，导致程序出现不可预知的错误。
2. 价值+1操作：c[i][j]++。为什么？因为我们的max_val初始值可以是0，表示手中没有宝物。如果地图中有价值为0的宝物，那么条件c[nx][ny] > max_val（即0 > 0）就不成立，无法拿起价值为0的宝物。但题目逻辑是允许拿的（价值0大于“没有”的状态）。一个巧妙的处理办法就是将所有价值加1，这样价值范围变为[1,13]，而初始状态max_val=0就能顺利拿起价值为1（原0）的宝物了。这是一种常见的偏移技巧。
3. 方向处理：这里将方向循环拆成了两个独立的if判断（向右、向下），逻辑更清晰，也避免了在循环内重复判断越界。
4. 初始化与取模：dp数组初始化为-1。每次累加方案数后立即取模% MOD，防止溢出。

经过记忆化，状态总数是n * m * 14 * 14，每个状态进行常数次转移，时间复杂度是O(nmk*V)，完全可以在规定时间内运行。

6. 记忆化搜索的通用范式与调试技巧

通过以上三个例子，我们可以总结出记忆化搜索的通用代码框架和心法。

6.1 通用四步法

1. 定义状态与DP数组：仔细分析问题，找出影响决策的所有变量，它们共同构成一个“状态”。用这些变量作为维度，定义记忆化数组dp。数组类型根据返回值确定（bool, int, long long等）。
2. 设计递归函数：函数参数与状态变量一一对应。函数返回值就是从该状态出发的答案（能否到达、方案数、最优值等）。
3. 实现递归逻辑：
   • 边界条件：首先处理递归终点（如到达目标、超出范围、不合法状态），直接返回结果。
   • 记忆化检查：在函数开头，检查dp[状态]是否已计算。是则直接返回。
   • 状态转移：根据题意，枚举当前状态的所有可能选择或下一步状态，递归调用函数，并根据子问题的结果计算当前状态的答案。
   • 保存并返回：将计算出的答案存入dp[状态]，然后返回。
4. 初始化与调用：在主函数中，初始化dp数组为“未计算”值（如-1，或一个不可能出现的值）。然后以初始状态调用递归函数。

6.2 常见问题与调试技巧

即使掌握了框架，实际编码中还是会遇到各种坑。下面是一些高频问题及解决方法。

问题1：记忆化为什么没生效？时间复杂度还是很高？

• 检查状态定义是否完整：是否漏掉了影响结果的隐藏变量？比如“混境之地”的背包状态t。
• 检查DP数组初始化：是否正确地用memset或循环初始化为了“未计算”标志？这个标志不能是函数可能返回的有效值。
• 检查记忆化代码位置：if (dp[state] != uncalculated) return dp[state];这行代码必须放在递归函数开头，在边界条件判断之后，但在任何复杂的计算或循环之前。
• 打印调试：在递归函数入口打印状态参数，如果看到大量相同的状态被重复调用，说明记忆化没起作用。

问题2：方案数巨大，结果不对或溢出？

• 及时取模：像“地宫取宝”这类计数问题，结果通常要对一个大数（如1e9+7）取模。必须在每次加法或乘法运算后立即取模，而不是最后才取模，因为中间结果可能已经溢出long long范围。
• 检查取模运算：(a + b) % MOD和(a % MOD + b % MOD) % MOD是等价的，但前者更简洁。确保MOD是const常量。

问题3：递归深度过大，导致栈溢出？

• 估算深度：递归深度通常等于搜索树的最大深度。在网格DFS中，深度可能是n+m。对于n,m=50，深度100是安全的。但对于n,m=1000的网格，深度2000可能接近或超过系统栈限制（通常1-8MB）。
• 解决方法：
  1. 改用迭代DP：如果问题可以用循环顺序求解，优先用迭代法。
  2. 调整系统栈（竞赛中可能不允许）：在C++中，可以用编译指令或ulimit -s unlimited（Linux）来扩大栈空间，但这并非良策。
  3. 优化状态：看是否能减少状态维度，或者用BFS+队列来避免深层递归。

问题4：如何选择“未计算”标志？

• 如果结果范围是[0, INF)，可以用-1。
• 如果结果可能是任意整数（包括负数），可以用一个特殊值，如-INF或0x3f3f3f3f（一个很大的数），但要确保这个值不会与合法结果冲突。
• 更通用的方法是使用一个单独的bool visited数组来记录状态是否被计算过。

6.3 记忆化搜索 vs 动态规划

这是初学者常问的问题。本质上，记忆化搜索就是动态规划的一种实现方式（自顶向下），而通常说的动态规划指的是自底向上的迭代填表法。

个人建议：对于新手，从记忆化搜索入手来理解动态规划的思想是极好的。它让你专注于“状态”和“转移”，而不用纠结于循环的顺序。当你对问题足够熟悉后，可以尝试将其改写为迭代形式，这往往能获得更好的常数性能，并且是面试官更期待的写法。

7. 举一反三：记忆化搜索的变体与拓展

掌握了基础模型，我们可以看看记忆化搜索还能解决哪些变体问题，这有助于你形成知识网络。

7.1 结合其他算法：DFS with Memoization on Graph

记忆化搜索不只用于网格，它可以用于任何有向无环图上的DP问题。例如，在有向图中找最长路径（关键路径问题）：

// 假设图用邻接表G存储，dp[u]表示从节点u出发能到达的最长路径长度 vector<int> dp(n, -1); int dfs_longest(int u) { if (dp[u] != -1) return dp[u]; int max_len = 0; for (int v : G[u]) { max_len = max(max_len, dfs_longest(v) + 1); // 边权为1 } return dp[u] = max_len; } // 对所有入度为0的节点调用dfs_longest，取最大值

这里，图必须是无环的，否则递归会陷入死循环。对于有环图，需要先进行拓扑排序或使用其他算法。

7.2 状态压缩与记忆化

当状态中的某个维度是集合（比如哪些点访问过）时，可以用位运算进行状态压缩，然后用整数作为DP数组的下标。经典的“旅行商问题”的DP解法就是状态压缩记忆化搜索。

// 假设有n个城市，从0号城市出发，最后回到0号，求最短环路。 // 状态：dp[mask][u] 表示已经访问过的城市集合为mask（二进制位表示），当前位于城市u，走完剩余城市回到0号点的最短距离。 int dp[1<<n][n]; int dfs_tsp(int mask, int u) { if (mask == (1<<n)-1) { // 所有城市都访问过 return dist[u][0]; // 返回当前城市到起点的距离 } if (dp[mask][u] != -1) return dp[mask][u]; int res = INF; for (int v = 0; v < n; ++v) { if (!(mask & (1<<v))) { // 城市v未访问 res = min(res, dfs_tsp(mask | (1<<v), v) + dist[u][v]); } } return dp[mask][u] = res; } // 初始调用：dfs_tsp(1, 0); // 从0号城市出发，mask中第0位为1

7.3 博弈类问题中的记忆化

记忆化搜索也常用于解决双方轮流操作、最优策略的博弈问题。例如，经典的“取石子游戏”：有一堆石子，每次可以取1个、3个或4个，无法取者输。判断先手是否必胜。

// dp[stones]：剩余stones个石子时，当前操作者是否必胜 vector<int> dp(n+1, -1); // -1未知，0必败，1必胜 bool canWin(int stones) { if (stones == 0) return false; // 没石子可取了，当前操作者输 if (dp[stones] != -1) return dp[stones]; // 当前操作者可以尝试取1,3,4个 // 如果存在一种取法，使得对手处于必败状态，则当前操作者必胜 if (stones >= 1 && !canWin(stones - 1)) return dp[stones] = 1; if (stones >= 3 && !canWin(stones - 3)) return dp[stones] = 1; if (stones >= 4 && !canWin(stones - 4)) return dp[stones] = 1; // 所有取法都会让对手进入必胜状态，则当前操作者必败 return dp[stones] = 0; }

这类问题的核心是：一个状态是“必胜态”，当且仅当存在一个操作能将它变为一个“必败态”；一个状态是“必败态”，当且仅当所有操作都将它变为“必胜态”。

从Fibonacci数列的递归优化，到迷宫路径的判定，再到复杂方案的计数，记忆化搜索像一根金线，串起了算法学习中这些看似离散的珍珠。它的核心思想——用空间换时间，存储重复子问题的解——是算法优化中最朴素也最强大的思想之一。我建议你在理解本文代码的基础上，去找LeetCode或蓝桥杯真题练习，比如“不同路径”、“零钱兑换”、“最长递增子序列”等问题，都可以用记忆化搜索优雅地解决。最开始可能会在状态设计上卡壳，多练几次，你就能快速抓住问题的关键变量。记住，写递归函数时，先别管效率，把暴力的、正确的逻辑写出来，然后再思考：这个函数的输出，是不是只由输入参数决定？如果是，就大胆地加上那个dp数组吧。