1. 从一道集训题说起汉诺塔为什么需要记忆化汉诺塔这个经典递归问题几乎每个学编程的人都在入门阶段写过。三根柱子、若干圆盘每次只能移动一个盘子大盘不能压在小盘上求把所有盘子从A柱移到C柱的最少步数。标准答案就是2的n次方减1递归三行代码搞定。但集训营里这道题显然不会让你只求步数它把汉诺塔的移动过程做了变形要求统计在特定移动规则下某种操作出现的次数而且数据规模不小直接递归会超时必须引入记忆化搜索来优化。我第一次碰到这类变形汉诺塔题目的时候直觉就是照着经典递归改一改加个计数器就完事了。结果提交上去直接超时因为经典汉诺塔的递归展开是指数级的n稍微大一点就炸了。后来才意识到这类题目的关键在于找到递归过程中的重复子问题用记忆化把已经算过的状态存下来避免重复计算。这道题的核心考点就是记忆化搜索在汉诺塔变形问题上的应用。这篇文章适合已经掌握递归基础、想进一步理解记忆化搜索实战应用的读者。我会从汉诺塔的递归本质讲起拆解这道题的状态定义思路给出完整的记忆化实现方案并分享我在调试过程中踩过的几个坑。不管你是正在准备算法竞赛还是想通过经典问题加深对记忆化的理解这篇内容都能给你一些可以直接复用的经验。2. 汉诺塔递归的本质与变形题的切入点2.1 经典汉诺塔的递归结构拆解经典汉诺塔的递归思路可以用一句话概括要把n个盘子从A移到C先把上面n-1个盘子从A移到B再把最大的盘子从A移到C最后把n-1个盘子从B移到C。这个过程中辅助柱的角色在不断切换。写成伪代码就是def hanoi(n, from_rod, to_rod, aux_rod): if n 1: move(from_rod, to_rod) return hanoi(n-1, from_rod, aux_rod, to_rod) move(from_rod, to_rod) hanoi(n-1, aux_rod, to_rod, from_rod)这个递归的调用次数是2的n次方减1每一步对应一次盘子移动。当n等于30的时候移动次数已经超过10亿暴力模拟根本跑不完。但注意递归树中存在大量结构相同的子问题比如多次出现“把k个盘子从某柱移到另一柱”的情况只是参数不同。这就是记忆化可以切入的地方。2.2 变形题到底变了什么这道集训题在经典汉诺塔基础上做了两个关键变形。第一它不满足于只求总步数而是要求统计在移动过程中从某一根柱子移动到另一根柱子的操作各出现了多少次。第二它可能改变了移动的规则或者初始条件比如指定了某些盘子的初始位置或者要求按照特定顺序输出六种移动方向的计数。具体来说六种移动方向分别是A到B、A到C、B到A、B到C、C到A、C到B。题目要求输出这六种操作各自发生的次数。如果还是用经典递归去模拟每一步时间复杂度无法接受。但如果我们把“将n个盘子从柱子X移动到柱子Y以柱子Z为辅助”定义为一个状态那么这个状态下的六种操作计数是可以被复用的。2.3 为什么记忆化是这道题的正解记忆化搜索的核心思想是对于相同的输入参数函数的返回值应该是一样的所以第一次算完之后把结果存起来下次再遇到同样的参数直接查表返回。在汉诺塔变形题中状态可以用三个参数来描述盘子数量n、起始柱from、目标柱to。辅助柱aux可以由from和to推导出来因为三根柱子中剩下的那根就是辅助柱。这样一来状态总数就是n乘以3乘以3n最多几十状态数非常有限。每个状态只需要计算一次后续直接查表。时间复杂度从指数级降到了多项式级这就是记忆化带来的质变。注意记忆化的前提是子问题重叠且无后效性。汉诺塔的递归结构天然满足这两点因为每个子问题的解只依赖于盘子数量和柱子编号与之前怎么移动过来的无关。3. 状态定义与转移方程的设计细节3.1 如何用三个参数唯一确定一个子问题状态定义是记忆化搜索最关键的一步。在这道题里我定义状态为dp[n][from][to]表示把n个盘子从from柱移动到to柱的过程中六种操作各自出现的次数。辅助柱aux就是三根柱子中既不是from也不是to的那一根。为什么三个参数就够了因为汉诺塔的递归过程中每次子问题的形式都是“把k个盘子从某柱移到另一柱”辅助柱由另外两根确定。盘子数量k决定了问题的规模from和to决定了移动的方向。这三个信息一旦确定整个移动过程就完全确定了六种操作的计数也就唯一确定了。这里有个容易忽略的点柱子的编号。通常我们用0、1、2来表示三根柱子那么aux就等于3减from减to。这个技巧在写代码的时候非常方便省去了条件判断。3.2 转移过程中六种计数的累加逻辑转移方程的思路是要计算dp[n][from][to]按照经典汉诺塔的三步走。第一步把n-1个盘子从from移到aux这一步的计数是dp[n-1][from][aux]。第二步把最大的盘子从from移到to这一步产生一次from到to的移动所以对应的计数加一。第三步把n-1个盘子从aux移到to这一步的计数是dp[n-1][aux][to]。把这三部分的六种操作计数逐项相加再加上第二步的那一次移动就得到了dp[n][from][to]的完整结果。写成公式就是dp[n][from][to] dp[n-1][from][aux] dp[n-1][aux][to] 一次(from, to)移动这个转移方程看起来简单但实现的时候需要用一个长度为6的数组来存储六种方向的计数每次合并两个子状态的时候要逐项相加。数组的下标映射关系要提前定义好比如0表示A到B1表示A到C以此类推。3.3 边界条件的处理与初始化递归的边界是n等于1的时候。此时只需要把唯一的盘子从from直接移到to六种计数中对应的那一项为1其余为0。这个边界条件非常清晰不需要额外处理。但有一个细节需要注意当n等于0的时候表示没有盘子需要移动六种计数全部为0。虽然在标准递归中n不会变成0但在某些变形题中可能会出现n为0的边界情况提前处理好可以避免数组越界或逻辑错误。初始化的另一个要点是记忆化数组的标记。我通常用一个特殊值来表示“尚未计算”比如把所有元素初始化为-1。每次进入递归函数先检查是否已经计算过如果计算过就直接返回。这个检查必须放在递归入口的最前面否则记忆化就失效了。4. 完整代码实现与逐段解析4.1 数据结构的选择与数组维度我选择用一个四维数组来存储记忆化结果维度分别是盘子数量n、起始柱from、目标柱to以及六种操作的计数。在Python中可以用嵌套列表在C中可以用三维数组加一个长度为6的一维数组。具体来说在C中可以定义long long dp[65][3][3][6]其中65是盘子数量的上限3是柱子数量6是操作种类数。用long long是因为当n较大时某些方向的移动次数可能超过int的范围。这一点很容易被忽略我一开始用int存结果n等于40的时候就溢出了调试了半天才发现是数据类型的问题。在Python中可以用一个字典来存储键是(n, from, to)元组值是长度为6的列表。字典的好处是不需要预先确定n的上限写起来更灵活。但字典的查找速度比数组慢一些如果n的上限不大用列表预分配会更高效。4.2 递归函数的参数设计与返回值递归函数接收三个参数n、from、to。返回值是一个长度为6的列表表示六种操作的计数。函数内部首先检查n是否为0如果是则返回全零列表。然后检查记忆化表中是否已有结果如果有则直接返回。接下来计算aux然后递归调用两次分别得到两个子状态的计数列表。把这两个列表逐项相加再根据from和to的值在对应的位置上加一。最后把结果存入记忆化表并返回。这里有一个优化技巧由于六种操作的计数是对称的某些状态之间可能存在对称关系可以利用对称性减少一半的计算量。但这样会增加代码的复杂度在竞赛中如果时间允许直接老老实实算所有状态更稳妥。4.3 六种移动方向的映射与输出格式六种移动方向的映射需要提前定义清楚。假设柱子编号为0、1、2那么六种方向可以按以下顺序排列下标方向含义00到1A到B10到2A到C21到0B到A31到2B到C42到0C到A52到1C到B在递归过程中当从from移动到to时需要根据from和to的值确定对应的下标。可以用一个二维数组来映射比如index[3][3]其中index[from][to]就是对应的下标。这样在累加的时候直接查表代码更简洁。输出的时候按照题目要求的顺序逐行打印即可。有些题目要求每个方向一行格式是“A到B: 次数”有些则要求用空格分隔。具体格式要看题目的输出要求这里不再赘述。#include bits/stdc.h using namespace std; long long dp[65][3][3][6]; bool vis[65][3][3]; int idx[3][3]; vectorlong long solve(int n, int from, int to) { vectorlong long res(6, 0); if (n 0) return res; if (vis[n][from][to]) { return vectorlong long(dp[n][from][to], dp[n][from][to] 6); } int aux 3 - from - to; vectorlong long left solve(n - 1, from, aux); vectorlong long right solve(n - 1, aux, to); for (int i 0; i 6; i) { res[i] left[i] right[i]; } res[idx[from][to]] 1; for (int i 0; i 6; i) { dp[n][from][to][i] res[i]; } vis[n][from][to] true; return res; } int main() { idx[0][1] 0; idx[0][2] 1; idx[1][0] 2; idx[1][2] 3; idx[2][0] 4; idx[2][1] 5; int n; cin n; vectorlong long ans solve(n, 0, 2); string names[6] {A到B, A到C, B到A, B到C, C到A, C到B}; for (int i 0; i 6; i) { cout names[i] : ans[i] endl; } return 0; }上面这段代码就是完整的实现框架。核心逻辑集中在solve函数中记忆化数组dp和访问标记vis配合使用。idx数组负责方向到下标的映射。主函数中初始化映射关系读入n调用递归函数最后按格式输出。5. 调试过程中踩过的三个坑5.1 记忆化数组未初始化导致的错误结果第一个坑是记忆化数组的初始化。我一开始只定义了dp数组忘记加vis标记数组结果在判断是否已经计算过的时候直接看dp数组的值是否为零。但问题是某些状态的六种计数可能恰好全是零比如n等于0的情况这时候就会误判为“尚未计算”导致重复递归甚至死循环。正确的做法是用一个独立的布尔数组来标记是否访问过或者把dp数组初始化为一个不可能出现的值比如-1。我后来改用了vis数组问题就解决了。这个坑看起来很低级但在紧张的比赛环境中很容易犯因为注意力都集中在转移方程上忽略了初始化这种细节。提示记忆化搜索中判断“是否已计算”的标记必须与结果数组分开或者用一个结果中不可能出现的值来初始化。不要依赖结果为零来判断。5.2 数据类型溢出与long long的必要性第二个坑是数据类型。当n等于40的时候某些方向的移动次数已经超过了int的最大值。我一开始用int存计数提交后答案错误但自己测试小数据又没问题。后来把中间结果打印出来发现出现了负数才意识到是溢出。汉诺塔的总移动次数是2的n次方减1当n等于40时这个数大约是1万亿远超int的21亿上限。虽然六种方向的计数各自大约是总步数的六分之一但某些方向在特定n下可能更集中仍然可能超过int范围。所以用long long是必须的这一点在题目没有明确说明数据范围的时候尤其要注意。5.3 递归深度与栈溢出的预防第三个坑是递归深度。当n等于60的时候递归深度会达到60层这在大多数环境下不会导致栈溢出。但如果n更大比如几百就需要考虑把递归改成迭代或者手动模拟栈。不过这道题的数据范围通常不会那么大因为状态数是n乘以9n太大数组也开不下。我在本地测试的时候把n设成了100结果程序直接崩溃报栈溢出错误。后来查了一下默认的栈大小大约是1到8兆每层递归的栈帧大约几十字节60层完全没问题。但如果n到了几千就必须改写成迭代形式了。这道题的实际数据范围应该在60以内所以递归写法是安全的。6. 从这道题延伸出的记忆化搜索通用套路6.1 什么类型的问题适合记忆化记忆化搜索适用于满足两个条件的问题第一问题可以分解为结构相同的子问题也就是存在重叠子问题第二子问题的解只依赖于有限的几个参数且这些参数的组合数量是多项式级别的。汉诺塔变形题完美符合这两个条件。子问题是“把k个盘子从某柱移到另一柱”参数只有三个组合数量有限。类似的还有斐波那契数列、背包问题的递归写法、区间动态规划等。反过来如果子问题的参数是连续变化的或者状态空间是指数级的记忆化就不适用了。6.2 状态压缩与维度优化的思路在某些记忆化问题中状态参数可能很多导致数组开不下。这时候需要考虑状态压缩把多个参数合并成一个整数或者利用对称性减少状态数量。以汉诺塔为例六种操作的计数其实存在对称关系。比如“把n个盘子从A移到C”和“把n个盘子从C移到A”的计数在方向上是对称的只是六种操作的顺序不同。如果题目只要求输出总数或者某些特定方向可以利用对称性把状态数减少一半。但这样做会增加代码的复杂度和出错概率在竞赛中需要权衡。6.3 记忆化与递推的取舍记忆化搜索和递推是解决同一类问题的两种思路。记忆化是自顶向下的写起来更接近问题的自然递归结构代码更直观。递推是自底向上的需要先确定计算顺序但通常运行效率更高因为没有递归调用的开销。对于汉诺塔变形题我倾向于用记忆化因为递归结构非常清晰转移方程容易推导。如果换成递推需要按照盘子数量从小到大依次计算所有柱子组合的状态代码量差不多但可读性稍差。当然如果对性能有极致要求递推是更好的选择。对比维度记忆化搜索递推代码直观性高贴近递归定义中需要确定顺序运行效率略低有递归开销高无递归开销空间复杂度相同相同适用场景状态转移复杂、顺序不明显状态转移简单、顺序明确7. 我在实际编码中的几点体会这道题我前前后后提交了五次才通过前四次分别栽在了初始化、数据类型和输出格式上。回过头来看题目本身的难度并不大但细节特别多任何一个环节出错都会导致答案错误或超时。第一个体会是记忆化搜索的代码框架要固定下来形成肌肉记忆。我现在写记忆化搜索都是固定的四步检查边界、检查记忆表、递归计算、存表返回。这个框架适用于绝大多数记忆化题目不需要每次重新设计。第二个体会是数据范围一定要看清楚。题目如果没有明确说n的上限就要根据题目背景和常见设定来推断。汉诺塔问题的n通常不会超过60因为2的60次方已经接近long long的上限了。如果n更大就需要用高精度或者取模运算。第三个体会是输出格式要严格对照题目要求。有些题目要求每个方向一行有些要求用空格分隔有些要求按照特定顺序输出。这些细节看似无关紧要但一旦弄错就是零分。我习惯在本地写一个格式化输出的函数把结果按照题目要求的格式打印出来方便对照检查。最后分享一个小技巧在调试记忆化搜索的时候可以在递归函数入口打印当前参数和返回值这样能直观地看到哪些状态被重复计算了哪些状态没有被正确缓存。这个方法帮我快速定位了好几次缓存失效的问题。
