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 - 1n等于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到B1代表A到C2代表B到A3代表B到C4代表C到A5代表C到B。这个顺序和题目常见的输出顺序一致。你可以在代码里写个注释标清楚避免自己回头看的时候懵。还有一个技巧用一个函数把“源柱和目标柱”转换成对应的下标。比如源是A、目标是B就返回0源是A、目标是C就返回1以此类推。这样在递归里移动盘子的时候直接调用这个函数拿到下标然后给计数数组对应位置加一干净利落。3.2 辅助柱的推导逻辑前面说了辅助柱不用作为状态维度但递归的时候必须知道辅助柱是谁。推导逻辑很简单三根柱子A、B、C已知两根第三根就是剩下的那根。用代码表达就是如果src和dst都不是某根柱子那这根就是aux。我习惯用一个数组或者简单的条件判断来实现。比如柱子用0、1、2表示那么aux 3 - src - dst。这个公式很优雅因为0123减去src和dst剩下的就是aux。用这个公式比写一堆if-else清爽得多也不容易出错。这个推导在递归里会频繁用到所以一定要确保逻辑正确。我建议你写完推导后手动验证几组src0、dst2aux应该是1src1、dst0aux应该是2。验证通过再往下写。3.3 数组相加的实现细节记忆化搜索里每个状态的结果是一个长度为6的数组。计算父状态时需要把子状态的数组逐位相加。这个操作看起来简单但有几个细节要注意。第一数组相加要逐位进行不能整体赋值。C里数组不能直接相加必须写循环。我一般写个辅助函数传入两个数组把第二个的每一位加到第一个上。这样代码复用性好也不容易漏位。第二注意加法的顺序。父状态的结果是三个子步骤结果的累加第一步的n-1个盘子从src到aux第二步的一个盘子从src到dst第三步的n-1个盘子从aux到dst。这三部分要全部加进去少加一部分答案就错了。第三第二步那个“一个盘子从src到dst”也要计入。很多人写着写着就忘了这一步因为它不是递归调用只是一次直接移动。但这一次移动是实实在在发生的必须给对应的计数加一。我踩过的坑就是忘了第二步的计数导致所有答案都偏小。后来我养成了一个习惯每次写完递归手动模拟n2的情况把每一步移动都列出来和代码输出对比。n2时总共移动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再返回。这个顺序不能乱否则可能重复计算或者返回错误值。还有一点n1是递归的边界这个状态也要存进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 参数计算与状态转移的验证写完代码不能直接交必须手动验证。我一般用n1、n2、n3三个规模来验证因为小规模可以手算能快速发现逻辑错误。n1时只有一个盘子从A移到C所以AC的次数是1其余五种是0。代码输出应该是0 1 0 0 0 0。这个最简单先确认。n2时手动模拟一下。第一步小盘子从A移到BAB加一。第二步大盘子从A移到CAC加一。第三步小盘子从B移到CBC加一。所以结果是AB1AC1BC1其余为0。代码输出应该是1 1 0 1 0 0。如果对不上说明递归的三步走有问题。n3时总移动次数是7。手动模拟会比较繁琐但可以用递推关系验证。n3的结果应该等于n2从A到B的结果加上一次A到C加上n2从B到C的结果。把n2的两个结果算出来相加再手动加一次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 答案偏小或偏大怎么排查答案不对是最常见的问题我把它分成两类偏小和偏大。答案偏小最常见的原因是漏加了某一步的计数。比如忘了第二步那个“最大的盘子直接移动”或者某次递归调用的结果没有累加进去。排查方法是手动模拟n2把每一步移动列出来和代码的中间结果对比。如果n2对但n3不对说明递归的某一步有问题重点检查辅助柱的推导和递归参数的传递。答案偏大通常是重复计算了。比如记忆化没生效同一个状态被算了多次并累加。排查方法是检查visited数组的标记和查询逻辑确保算过的状态直接返回而不是重新计算。还有一种可能是数组相加时把同一个数组加了两次检查addArray的调用次数。我遇到过一次答案偏大查了半天发现是递归函数里先查了表但表里存的值是错的因为存表的时候数组没复制对。后来改成用循环逐位复制问题解决。所以存表和取表的时候数组的复制一定要仔细。5.2 记忆化失效的典型场景记忆化失效是这道题最隐蔽的坑。代码看起来有查表有存表但实际没起作用复杂度还是指数级。常见原因有三个。第一个原因是状态设计不对。比如把辅助柱也作为状态维度导致状态空间变大但重复率降低。或者状态维度不够不同的子问题被当成同一个状态导致结果错误。这道题三个维度盘子数、源柱、目标柱是刚好的不多不少。第二个原因是查表和存表的条件不一致。比如查表时判断visited存表时忘了设置visited导致下次还是查不到。或者查表用的参数和存表用的参数不一致比如一个用src一个用dst这种错误很隐蔽。第三个原因是递归边界没有存表。n1的状态虽然简单但如果不存表每次遇到都要重新计算。虽然n1的计算很快但架不住次数多累积起来也会影响性能。养成所有状态都存表的习惯逻辑统一不容易出错。5.3 数组越界与初始化问题数组越界是C里最危险的错误因为它可能不报错但结果莫名其妙。这道题的dp数组是[MAXN][3][3][6]MAXN要开得比n的最大值大一点比如n最大60就开65。开小了会越界开大了浪费内存但安全。初始化问题也很关键。visited数组必须全部初始化为falsedp数组不需要初始化因为访问前一定会先判断visited。但如果用-1标记未计算那dp数组就要初始化为-1。两种方案选一种不要混用。还有一个细节如果多次调用solve函数比如多组测试数据visited数组要重新初始化。我一般把初始化放在main函数开头或者每组数据前memset一次。忘了重置visited会导致上一组的数据污染下一组这个坑在多组数据的题目里很常见。5.4 常见问题速查表问题现象可能原因排查方法解决方案答案偏小漏加某步计数手动模拟n2对比检查第二步直接移动是否计数答案偏大重复计算检查visited逻辑确保算过的状态直接返回超时记忆化失效打印状态访问次数检查状态设计和存表逻辑结果随机数组越界检查MAXN大小开大数组检查下标范围多组数据错误visited未重置检查初始化位置每组数据前memset输出格式错误多余空格或顺序错对比题目要求控制最后一个字符核对顺序这张表是我自己踩坑总结的基本上覆盖了这道题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。这道题我前前后后做了三遍第一遍纯递归超时第二遍记忆化但状态设计错了第三遍才完全正确。每次踩坑都让我对记忆化搜索的理解更深一层。汉诺塔这个题材看似简单但配合记忆化之后能考出很多东西状态设计、递归边界、数组操作、复杂度分析每一个都是算法竞赛的核心能力。如果你能把这道题彻底吃透以后再遇到类似的记忆化题目基本就是套模板的事了。