51个经典算法知识地图：从递归回溯到动态规划的复习指南

简介：这份文档面向ACM竞赛选手与算法学习者，系统整理了51个经典算法实例，覆盖递归、图论、动态规划、搜索与组合优化等核心领域，适合用来打牢算法基础、训练解题思维。压缩包内为1个doc文件，约1.77MB，共126页，每个实例均包含题目说明、解题思路、分析过程与可运行的源码，形成从理解到实现的完整闭环。内容从河内之塔、费式数列、巴斯卡三角形等入门递归题，延伸到八皇后、骑士走棋盘、老鼠走迷宫等搜索与回溯问题，再到背包问题、蒙地卡罗法求PI、Eratosthenes筛选求质数、超长整数运算等进阶主题，目录编排清晰，便于按知识点逐项研读。已有413人学习，读者可据此对照源码复现实验、理解算法设计取舍，并积累可迁移的解题套路，适合备赛刷题与日常算法训练使用。

1. 从 51 个经典算法看算法学习的知识地图

很多人复习算法时容易陷入一个误区：把「刷题数量」当成「掌握程度」。刷了几百道，遇到变体还是卡壳，原因往往不是题做少了，而是脑子里没有一张清晰的知识地图。《ACM51个经典算法大全》这份资料的价值，恰恰在于它用 51 个经典例子，把算法学习的主干脉络完整铺开了一遍——从递归、回溯、搜索，到排序、查找、动态规划，再到矩阵与数论，几乎覆盖了算法竞赛和课程复习的全部核心模块。

这份资料共 126 页，每个算法都配了题目说明、解题思路、分析过程和可运行的源码，适合两类人：一是正在系统学算法、需要一份结构化提纲的学习者；二是备考 ACM 或课程考试、想快速查漏补缺的复习者。下面按知识模块把这份资料重新梳理一遍，重点标出每个模块的核心思想、易错点和复习抓手。

2. 递归与回溯：从河内之塔到八皇后的统一框架

2.1 递归的三要素与河内之塔

河内之塔是理解递归的最佳入口。它的核心不是「怎么搬盘子」，而是「怎么把 n 个盘子的问题缩小成 n-1 个盘子的问题」。资料里的解法把柱子标为 A、B、C，当盘数超过 2 个时，把第三个以下的盘子「遮起来」，每次只处理两个盘子的三步操作：A→B、A→C、B→C，被遮住的部分交给递归处理。

递归写对的关键是三要素：递归出口、问题缩小、状态恢复。河内之塔的出口是n == 1直接搬，缩小是把 n-1 个盘子先移到辅助柱，状态恢复在回溯类问题里才真正体现。移动次数公式是2^n - 1，当 n=64 时约为 1.8×10^19 次，按每秒一次算要五千多亿年——这个数字本身就是对「指数爆炸」最直观的提醒。

void hanoi(int n, char A, char B, char C) { if (n == 1) { printf("Move sheet %d from %c to %c\n", n, A, C); // 递归出口：只剩一个盘子直接搬 } else { hanoi(n - 1, A, C, B); // 把上面 n-1 个盘子从 A 借 C 移到 B printf("Move sheet %d from %c to %c\n", n, A, C); // 把最大的盘子从 A 移到 C hanoi(n - 1, B, A, C); // 把 B 上的 n-1 个盘子借 A 移到 C } }

参数含义要记牢：第一个参数是盘数，后三个参数依次是「源柱、辅助柱、目标柱」。很多人写递归时把辅助柱和目标柱传反，程序不报错但结果全乱，这是最典型的翻车点。判断方法很简单：hanoi(n-1, A, C, B)里 C 是辅助、B 是目标，因为这一步的目标是把盘子挪到 B 上。

2.2 回溯与剪枝：八皇后、老鼠走迷宫、骑士走棋盘

八皇后是回溯法的标准模板。资料里的做法用三个数组做「分支修剪」：column[j]标记同列是否被占，rup[i+j]标记右上到左下对角线，lup[i-j+N]标记左上到右下对角线。放一个皇后就把三个标记置 0，回溯时再置回 1。

void backtrack(int i) { if (i > N) { showAnswer(); } // 出口：N 行都放好了，输出一组解 else { for (int j = 1; j <= N; j++) { if (column[j] && rup[i+j] && lup[i-j+N]) { // 三个方向都安全才放 queen[i] = j; column[j] = rup[i+j] = lup[i-j+N] = 0; // 占用 backtrack(i + 1); column[j] = rup[i+j] = lup[i-j+N] = 1; // 恢复现场 } } } }

这里最容易忽略的是对角线索引的偏移：i-j可能为负，所以加 N 保证下标非负。这个技巧在矩阵类回溯题里反复出现，记不住就会数组越界。

老鼠走迷宫（一）求单条路径，用success标志一旦找到就层层返回；老鼠走迷宫（二）求所有路径，反而更简单——走到出口就打印，然后退回上一格继续试，不需要success标志，但必须在递归返回后把maze[i][j]恢复为 0，否则其他路径会被已走过的格子堵死。骑士走棋盘则引入了 Warnsdorff 启发式：每步优先走「下一步出路最少」的位置，用贪心代替纯递归，在不使用递归的情况下有较高概率找到走法。这个思路和后面搜索章节的剪枝是一脉相承的。

3. 排序与查找：十种排序的分层记忆法

3.1 排序算法的三个梯队

资料里从第 33 到第 41 题连续讲了十种排序，硬背很容易混。梳理下来会发现它们其实分三个梯队：

记忆抓手是「改良类都是在基础类上打补丁」：Shell 排序是插入排序的改良，用增量序列让元素先大跨度移动；Shaker 排序是气泡排序的改良，双向扫描解决「小元素在末尾要跑很多趟」的问题；改良选择排序则用额外空间记录每趟的最小值和位置，减少交换次数。

3.2 快速排序的三个版本与合并排序

资料把快速排序拆成三个版本（第 37～39 题），这是很多人复习时的盲区。三个版本的差别主要在基准值（pivot）的选取和分割方式：版本一取固定位置做基准，版本二在分割时做双向扫描，版本三进一步优化了分割逻辑。理解快排的关键不是背代码，而是想清楚「分割完成后，基准左边的都不大于它，右边的都不小于它」这个不变量。

合并排序（第 40 题）是分治的标准范例：先递归把左右两半排好，再合并两个有序序列。它的稳定性和 O(n log n) 的稳定复杂度是最大优势，代价是需要 O(n) 的辅助空间。基数排序（第 41 题）则完全跳出比较框架，按个位、十位、百位依次分配收集，适合整数且位数不多的场景。

3.3 四种查找的适用边界

查找部分讲了循序搜寻（带卫兵）、二分搜寻、插补搜寻、费氏搜寻四种。二分搜寻是「搜寻原则的代表」，前提是数据必须有序，这是最容易被忽略的约束。插补搜寻在数据分布均匀时比二分更快，它用比例估算位置而不是固定取中点；费氏搜寻用斐波那契数分割区间，适合数据量大且不便频繁做除法的场景。卫兵技巧则是在数组末尾放一个待查值，省去每次循环的边界判断，属于「用空间换判断」的小优化。

4. 动态规划与数论：背包、大数与质数筛

4.1 背包问题的状态定义

背包问题（第 13 题）是动态规划的入门经典。核心是定义状态dp[i][j]表示「前 i 件物品、容量 j 下的最大价值」，转移方程是「不选第 i 件」和「选第 i 件」取较大值。资料里强调动态规划是解决此类组合优化问题的有效方法，复习时要能徒手写出二维版本，再理解一维滚动数组的优化——倒序遍历容量是防止同一物品被重复选取的关键，这个细节考试里经常设坑。

4.2 大数运算与数论基础

超长整数运算（第 16 题）处理超过标准整型范围的数，用数组或链表按位存储，逐位做加减乘除并处理进位借位。长 PI（第 17 题）则是大数运算的应用：用公式逐项计算 π 的更多位。数论部分包括 Eratosthenes 筛法求质数（第 15 题）、最大公因数与最小公倍数（第 18 题）、完美数（第 19 题）、阿姆斯壮数（第 20 题）。筛法的核心是「从 2 开始，把每个质数的倍数全部划掉」，时间复杂度 O(n log log n)，比逐个试除高效得多。

蒙地卡罗法求 PI（第 14 题）是概率算法的代表：在正方形内随机撒点，落在内切圆内的比例乘以 4 就是 π 的近似值。它说明算法不只有确定性解法，随机化也是一种正当思路。

5. 组合数学与矩阵：容易被低估的得分模块

5.1 排列组合与集合生成

第 27～31 题集中讲组合数学：排列组合、格雷码、产生可能的集合、m 元素集合的 n 个元素子集、数字拆解。格雷码的特点是相邻两个编码只有一位不同，生成时可以用「异或」或「镜像反射」两种思路。子集生成则是回溯的另一种形态——每个元素「选或不选」构成一棵二叉决策树。这部分内容在竞赛里出现频率高但容易被跳过，因为看起来「没有算法味」，实际上手写时边界条件特别多。

5.2 矩阵压缩与魔方阵

第 46～51 题是矩阵专题：稀疏矩阵、多维转一维、上三角/下三角/对称矩阵、奇数魔方阵、4N 魔方阵、2(2N+1) 魔方阵。稀疏矩阵用三元组（行、列、值）存储，只记非零元素；对称矩阵只存一半，用下标映射公式还原。魔方阵的填法有固定套路：奇数阶用「斜向上走、出界则绕回」的规则，4N 阶用对角线互补，2(2N+1) 阶则是奇数阶方法的扩展。这类题考的是「按规则模拟」的耐心，代码不长但下标推导容易错。

6. 易错点清单：这五个坑复习时最容易踩

易漏点一：递归的辅助柱与目标柱传反。为什么漏：河内之塔的递归调用参数多，凭感觉写很容易把 B、C 位置搞混，而程序不会报错。怎么补：每次写递归前先在纸上标出「源、辅、目标」三个角色，对照hanoi(n-1, A, C, B)的语义检查一遍。

易漏点二：回溯后忘记恢复现场。为什么漏：八皇后、迷宫类问题里，占用标记和路径标记的恢复语句藏在递归调用之后，调试时容易只盯着「找到解」的分支。怎么补：养成「占用与恢复成对出现」的书写习惯，写完立刻检查每个置 0 语句是否有对应的置 1。

易漏点三：二分查找忘记有序前提。为什么漏：二分代码太熟，拿到数组就写，忽略了数据未排序时结果无意义。怎么补：把「输入必须有序」写进函数注释，或在入口加断言检查。

易漏点四：大数运算的进位与借位处理不全。为什么漏：只考虑了正数相加，忽略了减法借位、乘法进位链、前导零清理。怎么补：把加减乘除拆成独立函数，每个函数单独测边界值（如 0、9、99）。

易漏点五：筛法数组越界。为什么漏：Eratosthenes 筛法里标记倍数时，循环上界写成i <= n而不是i * i <= n或j <= n，导致访问越界或漏筛。怎么补：明确数组大小开n+1，标记循环从i*i开始，写完后用小数据（n=30）手工验证一遍。

7. 复习落地：用 51 题做一次结构化自测

把这份资料当复习清单用，比从头到尾读一遍有效得多。具体做法是：先按本文的模块划分把 51 题归成五组——递归回溯（1、5～9、12）、排序查找（33～45）、动态规划与数论（13～20）、组合数学（27～32）、矩阵（46～51），然后每组挑两道题做「闭卷复现」：不看源码，只读题目说明，自己写出核心函数，再对照资料里的源码找差异。

自测时重点看三件事：一是递归出口写没写对，二是回溯的恢复语句全不全，三是复杂度和资料里的分析是否一致。差异最大的地方就是你的薄弱模块，回头把那一组题全部重做一遍。第 21～26 题（最大访客数、中序转后序、洗扑克牌、Craps 游戏、约瑟夫问题）属于应用型题目，适合放在最后当综合练习，检验前面模块的组合运用能力。

我自己的习惯是每复习完一个模块，就合上资料默写该模块的「一句话核心」——比如回溯就是「选、递归、撤销」，动态规划就是「定义状态、写转移、定边界」。写不出来说明还没真正吃透，回去重看那一题的解题思路部分。从那以后我每次复习算法都强制走一遍「先画地图、再分模块、最后闭卷复现」的流程，比盲目刷题省时间得多。希望这份梳理能帮到你，把 51 个经典算法真正变成自己脑子里的地图。

本文还有配套的精品资源，点击获取