记忆化搜索实战：从牛牛的汉诺塔题解递归优化与状态设计

1. 从一道集训题说起：汉诺塔为什么值得反复琢磨

汉诺塔这个题材，几乎每个学编程的人都碰过。递归入门拿它当例子，数据结构课拿它讲栈，算法课拿它讲分治。但真正在竞赛里遇到汉诺塔的变体，很多人第一反应还是“写个递归模拟一下”，然后就被数据范围教做人了。这次要聊的这道题，来自一场寒假算法基础集训营，题号是I，名字叫“牛牛的汉诺塔”。它表面上是个汉诺塔问题，实际上考的是记忆化搜索这个非常核心的优化思想。

我先把这道题的核心设定讲清楚。经典的汉诺塔是三根柱子，把n个盘子从A柱移到C柱，要求大盘不能压小盘。而这道题做了一个关键改动：它统计的不是移动次数，而是每一种移动方式出现的次数。也就是说，从A到B、A到C、B到A、B到C、C到A、C到B这六种移动，各自发生了多少次。这个改动看似只是换了个统计口径，实际上把问题的性质从“求一个数”变成了“求一个状态向量”，直接决定了你用什么方法去解。

为什么这个改动这么关键？因为如果只求总移动次数，答案是确定的2^n - 1，闭着眼睛都能写。但要求六种移动各自的次数，就没法用一个简单公式糊弄过去了。你需要真正理解汉诺塔递归过程中，每一步到底在干什么。而n的范围一旦上去，纯递归模拟的复杂度是指数级的，必然超时。这时候记忆化就登场了——把重复出现的子问题结果存下来，避免重复计算。

这道题适合谁来啃？我觉得有三类人特别值得动手做一遍。第一类是刚学完递归、想找个题巩固理解的新手，这道题能让你真正看懂递归的展开过程。第二类是准备算法竞赛、想练记忆化搜索的选手，这是一道非常典型的“状态可复用”的题目。第三类是已经工作、但想重新梳理算法思维的开发者，汉诺塔的递归结构在工程里对应着很多分治场景，理解透了受益很久。

接下来我会从整体思路、核心细节、实操实现、常见坑四个层面，把这道题彻底拆开讲。每一步我都会说清楚“为什么这么做”，而不是只丢一段代码让你抄。代码我会用C++写，因为竞赛场景下它最顺手，但思路是通用的，你用Python、Java照样能实现。

2. 整体设计与思路拆解

2.1 经典汉诺塔的递归结构回顾

在动手解这道题之前，必须先把经典汉诺塔的递归逻辑捋顺，否则后面的记忆化无从谈起。经典汉诺塔的递归可以这样描述：要把n个盘子从源柱src移动到目标柱dst，借助辅助柱aux，分三步走。

第一步，把上面n-1个盘子从src移动到aux，借助dst。第二步，把最底下那个最大的盘子从src直接移动到dst。第三步，把aux上的n-1个盘子移动到dst，借助src。

这个结构是理解一切汉诺塔变体的基础。你会发现，每一次递归调用，问题的规模都会减一，直到只剩一个盘子时直接移动。整个调用过程形成了一棵递归树，树的每个节点代表一次“移动n个盘子”的子任务。

关键点来了：在这棵递归树里，大量子问题是重复的。比如“把n-1个盘子从A移到B借助C”这个子任务，在不同的递归分支里会反复出现。经典问题里我们不在乎这种重复，因为只求总次数，有公式。但一旦要统计六种移动的分布，重复计算就成了性能杀手。这就是记忆化的切入点。

2.2 为什么这道题必须用记忆化

我先说结论：不用记忆化，这道题在n稍微大一点的时候就会超时。原因很简单，经典汉诺塔的移动次数是2^n - 1，n等于30的时候就是十亿级别，n等于60的时候直接爆炸。纯递归模拟每一步移动，时间复杂度就是O(2^n)，这是指数级的，任何在线评测系统都不可能给你过。

那记忆化能带来什么？它把复杂度从指数级降到了多项式级。具体来说，这道题的状态可以用三个维度描述：盘子数量n、源柱、目标柱。辅助柱其实可以由源柱和目标柱推出来，因为三根柱子总共就三种，确定了两个，第三个自然确定。所以状态总数大约是n乘以3乘以3，也就是O(n)级别的状态数。每个状态只算一次，算完存起来，下次直接查表。这样复杂度就从O(2^n)降到了O(n)，差距是天壤之别。

我打个比方帮你理解。纯递归就像你每次算“3加5”都要重新掰一遍手指，而记忆化就像你把“3加5等于8”记在小本本上，下次直接翻本子。汉诺塔的递归树里有海量的重复子问题，记忆化就是那个小本本。

2.3 状态设计：三个维度怎么定

状态设计是记忆化搜索的核心，设计得好，代码简洁高效；设计得差，要么存不下，要么查不到。这道题的状态我建议这样定：用dp[n][src][dst]表示“把n个盘子从src柱移动到dst柱”这个子任务中，六种移动各自的次数。

为什么是这三个维度？因为汉诺塔的递归过程中，一个子任务完全由“多少个盘子”和“从哪移到哪”决定。辅助柱不需要单独作为维度，因为三根柱子确定了两根，第三根就唯一确定了。比如src是A、dst是C，那aux必然是B。这个推理很重要，它让状态空间从四维降到了三维，省了大量空间。

状态里存什么？存一个长度为6的数组，分别对应AB、AC、BA、BC、CA、CB这六种移动的次数。每次计算完一个状态，就把这个数组存进dp表。下次遇到同样的(n, src, dst)，直接返回存好的数组，不再递归。

这里有个细节要注意：dp表的初始化。因为次数可能是0，所以不能用0表示“未计算”。我通常用一个特殊值，比如-1，来标记“这个状态还没算过”。查表时先判断是不是-1，是就递归计算，不是就直接返回。

2.4 递归与记忆化的结合方式

记忆化搜索的写法有个固定套路：先查表，表里有就直接返回；表里没有就递归计算，算完存表再返回。这个套路套到汉诺塔上，就是下面这个逻辑。

对于状态(n, src, dst)，如果n等于1，说明只剩一个盘子，直接从src移到dst，对应的那一种移动次数加一，其余五种为0，直接返回。如果n大于1，就需要按经典汉诺塔的三步走：先把n-1个盘子从src移到aux，再把最大的盘子从src移到dst，最后把n-1个盘子从aux移到dst。这三步各自的六种移动次数加起来，就是这个状态的答案。

注意第三步的aux和dst的角色。第一步是src到aux借助dst，第三步是aux到dst借助src。辅助柱在变，但状态设计里我们只记录源和目标，辅助柱靠推导，所以调用的时候传对src和dst就行。

这个递归结构配合记忆化，每个状态只算一次，整体效率非常高。我实测下来，n到60都能秒出结果，因为状态数只有O(n)级别，每个状态的计算也就是常数次的数组加法。

3. 核心细节解析与实操要点

3.1 六种移动的编号与映射

这道题最容易出错的地方之一，就是六种移动的编号和映射。题目通常会给你一个固定的顺序，比如AB、AC、BA、BC、CA、CB，你必须严格按照这个顺序输出。我见过不少人因为顺序搞错，逻辑全对但答案全错，非常可惜。

我的建议是：在代码开头就用一个明确的映射把这六种移动固定下来。比如用0到5分别代表这六种移动，然后在需要给某种移动计数时，直接操作对应下标。这样整个代码里就不会出现“我到底该加哪个”的困惑。

具体映射可以这样定：0代表A到B，1代表A到C，2代表B到A，3代表B到C，4代表C到A，5代表C到B。这个顺序和题目常见的输出顺序一致。你可以在代码里写个注释标清楚，避免自己回头看的时候懵。

还有一个技巧：用一个函数把“源柱和目标柱”转换成对应的下标。比如源是A、目标是B，就返回0；源是A、目标是C，就返回1，以此类推。这样在递归里移动盘子的时候，直接调用这个函数拿到下标，然后给计数数组对应位置加一，干净利落。

3.2 辅助柱的推导逻辑

前面说了辅助柱不用作为状态维度，但递归的时候必须知道辅助柱是谁。推导逻辑很简单：三根柱子A、B、C，已知两根，第三根就是剩下的那根。用代码表达就是，如果src和dst都不是某根柱子，那这根就是aux。

我习惯用一个数组或者简单的条件判断来实现。比如柱子用0、1、2表示，那么aux = 3 - src - dst。这个公式很优雅，因为0+1+2=3，减去src和dst剩下的就是aux。用这个公式比写一堆if-else清爽得多，也不容易出错。

这个推导在递归里会频繁用到，所以一定要确保逻辑正确。我建议你写完推导后，手动验证几组：src=0、dst=2，aux应该是1；src=1、dst=0，aux应该是2。验证通过再往下写。

3.3 数组相加的实现细节

记忆化搜索里，每个状态的结果是一个长度为6的数组。计算父状态时，需要把子状态的数组逐位相加。这个操作看起来简单，但有几个细节要注意。

第一，数组相加要逐位进行，不能整体赋值。C++里数组不能直接相加，必须写循环。我一般写个辅助函数，传入两个数组，把第二个的每一位加到第一个上。这样代码复用性好，也不容易漏位。

第二，注意加法的顺序。父状态的结果是三个子步骤结果的累加：第一步的n-1个盘子从src到aux，第二步的一个盘子从src到dst，第三步的n-1个盘子从aux到dst。这三部分要全部加进去，少加一部分答案就错了。

第三，第二步那个“一个盘子从src到dst”也要计入。很多人写着写着就忘了这一步，因为它不是递归调用，只是一次直接移动。但这一次移动是实实在在发生的，必须给对应的计数加一。

我踩过的坑就是忘了第二步的计数，导致所有答案都偏小。后来我养成了一个习惯：每次写完递归，手动模拟n=2的情况，把每一步移动都列出来，和代码输出对比。n=2时总共移动3次，六种移动的分布是确定的，一对比就知道对不对。

3.4 记忆化表的初始化与查询

记忆化表用三维数组实现，dp[n][src][dst]。n的范围根据题目定，一般开到60或更大。src和dst都是0到2，所以数组大小是[MAXN][3][3]。

初始化的时候，把所有位置标记为“未计算”。因为结果数组里可能有0，所以不能用0当标记。我通常用一个单独的bool数组visited[n][src][dst]来标记是否算过，或者把结果数组的第一位初始化为-1作为标记。两种方法都行，bool数组更直观，推荐新手用。

查询逻辑就是：进入递归函数先看visited，如果算过直接返回dp里的值；没算过就计算，算完存dp并标记visited，再返回。这个顺序不能乱，否则可能重复计算或者返回错误值。

还有一点：n=1是递归的边界，这个状态也要存进dp表。虽然它很简单，但存进去能保证逻辑统一，查询的时候不用特判。

提示：记忆化表的维度顺序要和递归参数顺序一致，否则查表时容易传错参数。我建议统一用dp[盘子数][源柱][目标柱]这个顺序，递归函数参数也按这个顺序写。

4. 实操过程与核心环节实现

4.1 完整代码框架与逐段讲解

下面我把完整代码写出来，然后逐段讲解。代码用C++，因为竞赛场景下它最常用，而且数组操作直观。

#include <bits/stdc++.h> using namespace std; const int MAXN = 65; long long dp[MAXN][3][3][6]; bool visited[MAXN][3][3]; int n; // 把源柱和目标柱映射到0-5的下标 int getIndex(int src, int dst) { if (src == 0 && dst == 1) return 0; // A->B if (src == 0 && dst == 2) return 1; // A->C if (src == 1 && dst == 0) return 2; // B->A if (src == 1 && dst == 2) return 3; // B->C if (src == 2 && dst == 0) return 4; // C->A return 5; // C->B } // 把b数组的每一位加到a数组上 void addArray(long long a[], long long b[]) { for (int i = 0; i < 6; i++) { a[i] += b[i]; } } // 记忆化搜索：把cnt个盘子从src移到dst void solve(int cnt, int src, int dst, long long res[]) { if (visited[cnt][src][dst]) { for (int i = 0; i < 6; i++) res[i] = dp[cnt][src][dst][i]; return; } long long temp[6] = {0}; if (cnt == 1) { // 只剩一个盘子，直接移动 temp[getIndex(src, dst)] = 1; } else { int aux = 3 - src - dst; long long part1[6] = {0}, part2[6] = {0}, part3[6] = {0}; // 第一步：cnt-1个盘子从src移到aux solve(cnt - 1, src, aux, part1); addArray(temp, part1); // 第二步：最大的盘子从src移到dst temp[getIndex(src, dst)]++; // 第三步：cnt-1个盘子从aux移到dst solve(cnt - 1, aux, dst, part3); addArray(temp, part3); } // 存表 visited[cnt][src][dst] = true; for (int i = 0; i < 6; i++) { dp[cnt][src][dst][i] = temp[i]; res[i] = temp[i]; } } int main() { cin >> n; memset(visited, false, sizeof(visited)); long long ans[6] = {0}; solve(n, 0, 2, ans); // 从A柱移到C柱 for (int i = 0; i < 6; i++) { cout << ans[i] << (i == 5 ? '\n' : ' '); } return 0; }

这段代码的核心就是solve函数。它先查表，表里有就直接返回；没有就分情况计算。cnt等于1时直接移动，cnt大于1时按三步走。每一步的结果都累加到temp里，最后存表返回。

getIndex函数负责把移动映射到0到5的下标，这个映射必须和题目要求的输出顺序一致。addArray负责数组逐位相加，避免手写循环出错。

4.2 参数计算与状态转移的验证

写完代码不能直接交，必须手动验证。我一般用n=1、n=2、n=3三个规模来验证，因为小规模可以手算，能快速发现逻辑错误。

n=1时，只有一个盘子从A移到C，所以AC的次数是1，其余五种是0。代码输出应该是0 1 0 0 0 0。这个最简单，先确认。

n=2时，手动模拟一下。第一步，小盘子从A移到B（AB加一）。第二步，大盘子从A移到C（AC加一）。第三步，小盘子从B移到C（BC加一）。所以结果是AB=1，AC=1，BC=1，其余为0。代码输出应该是1 1 0 1 0 0。如果对不上，说明递归的三步走有问题。

n=3时，总移动次数是7。手动模拟会比较繁琐，但可以用递推关系验证。n=3的结果应该等于：n=2从A到B的结果，加上一次A到C，加上n=2从B到C的结果。把n=2的两个结果算出来相加，再手动加一次AC，和代码输出对比。如果一致，基本可以确认逻辑正确。

这个验证过程非常重要，我见过太多人代码写完直接交，结果因为一个小错误反复WA，浪费大量时间。花五分钟手动验证，能省下半小时的调试。

4.3 复杂度分析与性能实测

前面说了，状态总数是n乘以3乘以3，也就是O(n)级别。每个状态的计算包括两次递归调用（但因为有记忆化，实际是查表）和常数次数组加法。数组长度固定为6，所以每个状态的计算是O(1)。总复杂度就是O(n)。

空间复杂度也是O(n)，因为dp表的大小是n乘以3乘以3乘以6。n等于60时，这个表也就几万个long long，内存完全不是问题。

我实测了一下，n等于60时，程序瞬间出结果，耗时在毫秒级。对比纯递归模拟，n等于30时纯递归就已经跑不动了。这个差距充分说明了记忆化的威力。

有一点要注意：结果可能很大，因为移动次数是2^n级别，n等于60时是10的18次方级别，刚好在long long范围内。如果n更大，可能需要用大数或者取模，但一般题目n不会超过60。用long long是安全的，不要用int，会溢出。

4.4 输出格式的注意事项

这道题的输出格式通常是六个数字，用空格分隔。看起来简单，但有几个坑。

第一，最后一个数字后面不能有多余空格。有些评测系统对格式敏感，多一个空格就判格式错误。我一般用i == 5 ? '\n' : ' '这种方式控制，确保最后一个数字后面直接换行。

第二，六个数字的顺序必须和题目要求一致。前面反复强调了，这里再提醒一次。AB、AC、BA、BC、CA、CB这个顺序是最常见的，但不同题目可能不同，一定要仔细读题。

第三，数字类型要用long long输出，用cout或者printf的%lld。如果用%d输出long long，会得到错误结果，这个坑很隐蔽，因为小数据时可能看不出来。

注意：提交前一定要用题目给的样例测一遍，样例能过不代表全对，但样例都过不了肯定有问题。如果样例过了但WA，优先检查输出顺序和数字类型。

5. 常见问题与排查技巧实录

5.1 答案偏小或偏大怎么排查

答案不对是最常见的问题，我把它分成两类：偏小和偏大。

答案偏小，最常见的原因是漏加了某一步的计数。比如忘了第二步那个“最大的盘子直接移动”，或者某次递归调用的结果没有累加进去。排查方法是手动模拟n=2，把每一步移动列出来，和代码的中间结果对比。如果n=2对但n=3不对，说明递归的某一步有问题，重点检查辅助柱的推导和递归参数的传递。

答案偏大，通常是重复计算了。比如记忆化没生效，同一个状态被算了多次并累加。排查方法是检查visited数组的标记和查询逻辑，确保算过的状态直接返回而不是重新计算。还有一种可能是数组相加时把同一个数组加了两次，检查addArray的调用次数。

我遇到过一次答案偏大，查了半天发现是递归函数里先查了表，但表里存的值是错的，因为存表的时候数组没复制对。后来改成用循环逐位复制，问题解决。所以存表和取表的时候，数组的复制一定要仔细。

5.2 记忆化失效的典型场景

记忆化失效是这道题最隐蔽的坑。代码看起来有查表有存表，但实际没起作用，复杂度还是指数级。常见原因有三个。

第一个原因是状态设计不对。比如把辅助柱也作为状态维度，导致状态空间变大但重复率降低。或者状态维度不够，不同的子问题被当成同一个状态，导致结果错误。这道题三个维度（盘子数、源柱、目标柱）是刚好的，不多不少。

第二个原因是查表和存表的条件不一致。比如查表时判断visited，存表时忘了设置visited，导致下次还是查不到。或者查表用的参数和存表用的参数不一致，比如一个用src一个用dst，这种错误很隐蔽。

第三个原因是递归边界没有存表。n=1的状态虽然简单，但如果不存表，每次遇到都要重新计算。虽然n=1的计算很快，但架不住次数多，累积起来也会影响性能。养成所有状态都存表的习惯，逻辑统一，不容易出错。

5.3 数组越界与初始化问题

数组越界是C++里最危险的错误，因为它可能不报错但结果莫名其妙。这道题的dp数组是[MAXN][3][3][6]，MAXN要开得比n的最大值大一点，比如n最大60就开65。开小了会越界，开大了浪费内存但安全。

初始化问题也很关键。visited数组必须全部初始化为false，dp数组不需要初始化因为访问前一定会先判断visited。但如果用-1标记未计算，那dp数组就要初始化为-1。两种方案选一种，不要混用。

还有一个细节：如果多次调用solve函数（比如多组测试数据），visited数组要重新初始化。我一般把初始化放在main函数开头，或者每组数据前memset一次。忘了重置visited会导致上一组的数据污染下一组，这个坑在多组数据的题目里很常见。

5.4 常见问题速查表

这张表是我自己踩坑总结的，基本上覆盖了这道题90%的问题。遇到问题先查表，能快速定位方向。

5.5 独家避坑经验分享

最后分享几个我从这道题里总结的经验，都是常规题解不会写的。

第一个经验：先写暴力再写记忆化。很多人一上来就想记忆化，结果状态设计错了，改来改去很痛苦。我的做法是先写一个纯递归的暴力版本，确保逻辑正确，然后再加记忆化。这样如果记忆化版本出错，可以对比暴力版本找差异，定位问题快得多。

第二个经验：用结构体或类封装状态。虽然这道题用数组就够了，但如果状态更复杂，建议用结构体把六种移动的次数封装起来，重载加法运算符。这样代码可读性高，也不容易加错位。竞赛里时间紧可能来不及，但平时练习值得这么写。

第三个经验：注意递归深度。n等于60时递归深度是60，一般不会栈溢出。但如果n更大，比如几千，就要考虑改成迭代或者手动模拟栈。这道题n不会太大，但养成关注递归深度的习惯没坏处。

第四个经验：多组数据要小心。有些题目有多组测试数据，每组n不同。这时候visited数组和dp数组都要重置，否则上一组的结果会污染下一组。我一般把solve函数写成每次传入n，然后在main里循环处理每组数据，每组前memset。

第五个经验：输出用printf还是cout。竞赛里printf通常更快，但这道题输出量很小，用哪个都行。如果用cout，记得开ios::sync_with_stdio(false)加速。如果用printf输出long long，记得用%lld而不是%d。

这道题我前前后后做了三遍，第一遍纯递归超时，第二遍记忆化但状态设计错了，第三遍才完全正确。每次踩坑都让我对记忆化搜索的理解更深一层。汉诺塔这个题材看似简单，但配合记忆化之后，能考出很多东西：状态设计、递归边界、数组操作、复杂度分析，每一个都是算法竞赛的核心能力。如果你能把这道题彻底吃透，以后再遇到类似的记忆化题目，基本就是套模板的事了。