汉诺塔移动次数统计：记忆化搜索与状态设计详解-北京尧图网络

1. 从一道集训题说起汉诺塔为什么值得反复琢磨汉诺塔这个经典问题几乎每个学编程的人都遇到过。递归入门靠它算法课讲分治靠它就连面试热身题也经常拿它开刀。但大多数人在写完那个经典的递归函数、打印出移动步骤之后就觉得自己“会了”。直到遇到这道题——统计汉诺塔在最优移动策略下各个柱子上移动次数的分布情况才发现原来这个看似简单的模型里藏着不少门道。这道题的核心要求是这样的给定n个盘子的经典汉诺塔在最优移动方案也就是最少步数方案下统计从A柱移动到B柱、A到C、B到A、B到C、C到A、C到B这六种移动各发生了多少次。n的范围不小直接递归模拟会超时必须找到更高效的统计方法。为什么这道题值得单独拿出来讲因为它把三个东西揉在了一起经典递归结构的理解、记忆化思想的运用、以及状态设计的技巧。很多人做这道题的第一反应是“我直接模拟不就行了”然后被数据范围教做人。第二反应是“那我用记忆化搜索”但状态怎么定义、怎么转移又卡住了一批人。我见过不少人在这一步反复调试最后发现是自己状态转移写漏了或者写重了。这篇文章适合两类人看一类是正在刷算法题、想搞懂记忆化搜索到底怎么落地的朋友另一类是对汉诺塔问题本身感兴趣、想知道它还能玩出什么花样的算法爱好者。我会从最朴素的思路开始一步步推到记忆化方案把每一步的“为什么”讲清楚最后给出可以直接参考的实现和几个我踩过的坑。2. 朴素递归为什么不够用先算一笔账2.1 经典汉诺塔的递归结构回顾先把经典汉诺塔的递归逻辑捋一遍。要把n个盘子从A柱借助B柱移动到C柱分三步走把上面n-1个盘子从A柱借助C柱移动到B柱把最底下那个最大的盘子从A柱直接移动到C柱把B柱上的n-1个盘子借助A柱移动到C柱。这个结构是理解一切后续优化的基础。用代码表示就是def hanoi(n, src, aux, dst): if n 0: return hanoi(n - 1, src, dst, aux) # 移动第n个盘子src - dst hanoi(n - 1, aux, src, dst)这个递归的时间复杂度是O(2^n)因为总移动次数就是2^n - 1。当n到30以上的时候2^30大约是十亿级别模拟一遍就已经很吃力了更别说还要统计六种移动的分布。2.2 直接模拟的复杂度瓶颈在哪里有人可能会想我不就是多统计几个计数器吗能有多慢问题在于统计本身不增加复杂度但递归展开的节点数本身就是指数级的。每展开一个节点你都要做一次计数操作总操作次数和移动次数同阶也就是O(2^n)。n30的时候十亿次操作在一般的评测环境下基本就是超时的命。更关键的是这道题里n可能达到60甚至更大具体范围看题目设定2^60是一个天文数字任何基于模拟的思路都不可能通过。所以必须换思路我们不关心具体的移动序列只关心“在最优策略下某种移动发生了多少次”。这就提示我们能不能把“把n个盘子从某柱移到另一柱”这个过程所对应的六种移动次数直接作为一个整体来递推计算答案是肯定的这就是记忆化搜索或者递推DP的核心切入点。2.3 从“模拟过程”转向“统计状态”的思路转换这里有一个思维上的关键跳跃不要去想“每一步怎么走”而是去想“一个子问题对应哪些移动这些移动的次数能不能由更小的子问题组合出来”。举个例子。把n个盘子从A借助B移到C这个过程可以拆成把n-1个盘子从A借助C移到B这部分产生的移动统计记为子问题1的结果把最大的盘子从A移到C这是一次A到C的移动把n-1个盘子从B借助A移到C这部分产生的移动统计记为子问题2的结果。那么整个问题的六种移动次数就等于子问题1的统计一次A到C 子问题2的统计。注意这里的“子问题1”和“子问题2”虽然都是n-1个盘子的移动但它们的起点、辅助点、终点不同所以对应的统计结果也不同。这就引出了状态定义的问题我们需要区分不同“起点-辅助-终点”组合下的统计结果。而汉诺塔的柱子只有三根所以本质上只有三种不同的“角色分配”方式哪个柱子当起点、哪个当辅助、哪个当终点每种方式对应一个统计向量。3. 记忆化搜索的状态设计与转移推导3.1 状态怎么定义才不重不漏三根柱子我们给它们编号0、1、2。一个子问题可以描述为把n个盘子从柱子from借助柱子aux移动到柱子to。由于三根柱子的角色是轮换的我们可以把状态定义为dp[n][from][to]其中aux由3 - from - to唯一确定因为三根柱子的编号之和是0123。每个状态dp[n][from][to]存储一个长度为6的数组分别表示六种移动的次数。六种移动按照起点和终点的有序对来区分(0,1)、(0,2)、(1,0)、(1,2)、(2,0)、(2,1)。这样定义之后状态总数是n乘以3乘以2也就是6n个状态每个状态存6个计数空间完全可控。为什么不用把aux也放进状态因为三根柱子中确定了from和to剩下的那根自然就是aux没有歧义。这样定义既简洁又不丢信息。3.2 转移方程的推导过程对于状态dp[n][from][to]设aux 3 - from - to。根据经典汉诺塔的三步拆解第一步把n-1个盘子从from借助to移到aux对应状态dp[n-1][from][aux] 第二步把最大的盘子从from移到to这是一次移动在统计数组的对应位置加1 第三步把n-1个盘子从aux借助from移到to对应状态dp[n-1][aux][to]。所以转移方程就是dp[n][from][to] dp[n-1][from][aux] dp[n-1][aux][to] dp[n][from][to][move(from, to)] 1其中move(from, to)表示把(from, to)这个有序对映射到0到5的某个下标。边界条件当n0时不需要任何移动六种计数全为0。这个转移的正确性依赖于一个前提最优策略下n个盘子的移动方案是唯一的在不考虑对称等价的情况下。实际上经典汉诺塔的最优方案确实是唯一的因为最大的盘子必须移动一次而在它移动之前上面的n-1个盘子必须全部移到辅助柱上之后又必须全部移到目标柱上每一步都没有选择余地。所以这个递推是精确的不会漏算也不会多算。3.3 记忆化与递推的取舍有了转移方程实现方式有两种自顶向下的记忆化搜索和自底向上的递推。记忆化搜索的写法更贴近递归思维代码结构清晰而且不需要考虑计算顺序。但缺点是递归深度可能较大n很大的时候有栈溢出的风险不过在Python里可以调高递归限制在C里一般问题不大。递推的写法需要先确定计算顺序从小到大枚举n对于每个n枚举所有(from, to)组合。由于dp[n]只依赖于dp[n-1]所以可以按n递增的顺序计算甚至可以用滚动数组优化空间。我个人的习惯是如果状态转移比较直观、依赖关系简单优先写递推因为可控性更强如果状态转移涉及复杂的条件判断或者依赖关系不明显用记忆化搜索更省心。这道题两种方式都很适合下面我分别给出实现。4. 完整实现与关键细节说明4.1 记忆化搜索版本先看记忆化搜索的写法。用一个三维数组memo来缓存结果memo[n][from][to]存储一个长度为6的列表。为了避免重复计算每次进入递归先查memo。import sys sys.setrecursionlimit(100000) def solve(): n int(input()) # memo[n][from][to] [c01, c02, c10, c12, c20, c21] memo {} def move_idx(a, b): # 把有序对映射到0-5 mapping {(0,1):0, (0,2):1, (1,0):2, (1,2):3, (2,0):4, (2,1):5} return mapping[(a, b)] def dp(n, frm, to): if n 0: return [0, 0, 0, 0, 0, 0] key (n, frm, to) if key in memo: return memo[key] aux 3 - frm - to res1 dp(n - 1, frm, aux) res2 dp(n - 1, aux, to) res [res1[i] res2[i] for i in range(6)] res[move_idx(frm, to)] 1 memo[key] res return res ans dp(n, 0, 2) # 从柱子0借助柱子1移到柱子2 print(ans) solve()这段代码里有一个细节值得注意memo用字典而不是三维列表是因为n的范围可能很大开三维列表可能内存吃紧而字典只存储实际访问到的状态。实际上对于每个n只有6种(from, to)组合会被访问到所以总状态数是6n用字典完全没问题。另一个细节是move_idx的映射。六种移动的顺序必须和最终输出要求的顺序一致否则答案会错位。我在实现的时候习惯先把映射关系写死避免后面搞混。4.2 递推版本与滚动数组优化递推版本的思路是从n1开始逐层计算所有(from, to)组合的统计结果。def solve_iter(): n int(input()) mapping {(0,1):0, (0,2):1, (1,0):2, (1,2):3, (2,0):4, (2,1):5} # prev[frm][to] 表示 n-1 个盘子的统计 prev [[[0]*6 for _ in range(3)] for _ in range(3)] for i in range(1, n 1): cur [[[0]*6 for _ in range(3)] for _ in range(3)] for frm in range(3): for to in range(3): if frm to: continue aux 3 - frm - to r1 prev[frm][aux] r2 prev[aux][to] for k in range(6): cur[frm][to][k] r1[k] r2[k] cur[frm][to][mapping[(frm, to)]] 1 prev cur ans prev[0][2] print(ans)这个版本的时间复杂度是O(n)空间复杂度如果不优化是O(1)因为每层只保留prev和cur两个3x3x6的数组。实际上3x3x6很小完全不需要滚动数组但滚动数组的写法更清晰地表达了“只依赖上一层”这个事实。4.3 输出格式与边界情况处理题目通常要求输出六个数分别对应六种移动的次数。输出顺序一定要和题目要求一致。我见过有人因为输出顺序搞错本地测试样例过了但提交WA的情况。建议在代码里把映射关系写成常量输出的时候按照映射顺序依次打印。边界情况主要是n0和n1。n0时所有计数为0n1时只有一次从起点到终点的移动。这两种情况在递推和记忆化里都能自然处理不需要特判。但如果你在写代码的时候手动处理了n0要注意返回的数组长度必须是6否则后面拼接会出错。还有一个容易忽略的点当n很大时计数值可能超出32位整数范围。2^60大约是1.15e18在64位整数范围内最大约9.2e18所以用64位整数存储是安全的。但如果n更大就需要用大整数或者取模。具体看题目要求这道题一般n不会超过60所以64位整数够用。5. 常见问题与排查技巧实录5.1 答案对不上样例的几种典型原因第一种移动映射搞反了。比如把(0,1)映射到了(1,0)的位置。这种错误在本地测试时如果样例恰好对称可能看不出来但提交就WA。排查方法是手动构造一个小例子比如n1看看输出是不是只有一次从起点到终点的移动。第二种辅助柱计算错误。aux 3 - frm - to这个公式在三根柱子编号为0、1、2时成立但如果你的编号是1、2、3公式就变成6 - frm - to。这种错误很隐蔽因为递归逻辑看起来是对的但辅助柱选错了会导致整个统计偏移。第三种记忆化键值冲突。如果用字典做memo键必须包含n、frm、to三个维度。有人只用了(n, frm)做键忽略了to的不同会导致结果不同这样会返回错误缓存。5.2 递归深度与性能的平衡Python的默认递归深度是1000当n超过1000时虽然这道题n不会那么大递归会爆栈。解决办法是sys.setrecursionlimit调高限制或者改用递推。在C里递归深度一般不是问题但如果是n10^5这种极端情况还是递推更稳妥。性能方面记忆化搜索的每个状态只计算一次总计算量是O(n)非常快。递推也是O(n)。两者的常数差异不大选择哪种主要看个人习惯和代码可读性。5.3 从这道题延伸出的通用记忆化技巧这道题体现了一个通用的记忆化模式当问题的结构具有自相似性且子问题的解可以组合成原问题的解时就可以考虑记忆化。关键在于找到合适的状态定义使得状态数量可控且转移方程清晰。具体到汉诺塔统计问题状态定义的精髓在于“用角色而不是具体柱子编号来描述子问题”。因为三根柱子的角色是对称的我们只需要知道“起点是谁、终点是谁”辅助柱自然确定。这种“角色化”的状态定义方式在很多组合问题里都有应用比如某些棋盘游戏的状态压缩、某些排列组合的递推等。另外这道题也提醒我们不要一看到“模拟”就真的去模拟。先分析问题的结构看看能不能把“过程”转化为“状态的组合”。很多时候统计量本身就可以作为状态的一部分来递推而不需要真的把过程走一遍。6. 我个人在实际操作中的几点体会这道题我第一次做的时候直接写了个递归模拟结果n25就跑了好几秒提交果断TLE。后来想到用记忆化但状态定义卡了很久一开始想把aux也放进状态导致状态数翻倍虽然也能过但不够优雅。后来发现aux可以由from和to唯一确定状态数直接减半代码也简洁了很多。另一个体会是关于输出顺序的。我习惯在代码里把六种移动的映射写成一个字典输出的时候按照字典的键顺序打印。但有一次我改了映射的顺序忘了同步改输出结果样例过了但提交WA查了半天才发现是输出顺序和题目要求不一致。从那以后我养成了一个习惯把映射关系写成常量输出和统计都用同一份常量避免不一致。最后说一个调试技巧。如果答案不对先用手算的小例子n1、n2验证。n1时只有一次移动n2时有三次移动统计结果很容易手算出来。用这两个例子对拍能快速定位是状态转移错了还是输出格式错了。如果小例子对但大例子错那多半是整数溢出或者记忆化键值冲突的问题。这道题虽然披着“汉诺塔”的外衣但核心考点是记忆化搜索的状态设计。把这道题吃透以后再遇到类似的“统计某种操作在最优策略下的次数”的问题就能很快找到切入点。

汉诺塔移动次数统计：记忆化搜索与状态设计详解

相关推荐

Scrapy日志系统实战：配置、优化与常见问题排查

Ubuntu离线中文语音识别实战：从环境搭建到效果调优

DeepSeek实战手册：环境配置、LoRA微调与推理排错全指南

更多资讯

sim-use 3分钟上手：observe-act-verify循环让AI验证自己写的移动App

智谱刚把 GLM-5.3 搬上 Amazon Bedrock，股价应声涨近 5%：国产大模型出海怎么突然就火了

C++手写CSV解析器：从状态机到流式处理实战

Pomotroid 土耳其语本地化实践：基于 Paraglide 的 8 语言架构与新增 locale 全流程

openJiuwen DeepSearch 研究规划提示模板（planner/user.md）深度解析：从 Jinja 渲染到计划生成的全链路实现

【宠粉赠书】分布式系统性能优化：方法与实践——用 TaoToken 统一 Key 打通压测与调优链路

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？