很多学《算法设计与分析》的同学做到第二章“递归与分治策略”的习题时最容易卡住的往往不是语法而是怎么把一段自然语言描述翻译成递归关系。习题2.5在我手头这本教材里就是典型代表题目叫“半数集问题”给定一个自然数 n允许在它左侧不断添加不超过当前首位数字一半的自然数问最终能生成多少个互不相同的数。题面短到只有两行蕴含的知识点却一点不少递归定义、递推方程、复杂度分析、动态规划优化全都能在这一道题里练到。无论你手上教材的习题2.5是不是这道题这套分析框架都可以直接复用因为递归与分治这一章后续的题目基本都长在同一副骨架上。1. 习题2.5究竟在考什么1.1 半数集问题题面与直觉陷阱题目通常这样描述对自然数 n可以在它左边添加一个不超过 n 的一半的自然数得到新数新数还能继续按同样规则往左添加。比如 n 6可以先加 1 得到 16加 2 得到 26加 3 得到 36而 26 还可以继续在左边加 1得到 12636 也可以加 1 得到 136。把这些能生成的数放在一起记作集合 set(6) {6, 16, 26, 126, 36, 136}一共 6 个元素。这里就是第一个直觉陷阱很多人以为只允许加一次前缀算出 6、16、26、36 四个就收工漏掉了继续扩展的 126 和 136。这道题叫“半数集”不叫“半数加前缀”考的就是你能不能意识到新生成的数仍然满足同一个规则。递归定义的“自嵌套”性质恰恰是分治策略里最容易被忽略、也最值得反复强调的东西。1.2 从一道小题看课程要求的三种核心能力为什么这么一道小习题能成为整个第二章作业里讨论度最高的一题因为“算法设计与分析”这门课要训练的核心能力它全部覆盖到了。第一是建模能力。把“不断加前缀”这个操作过程翻译成数学上的递推关系这是从自然语言到算法语言的关键跳跃。很多同学代码基础不差但遇到这种题就无从下手缺的正是这一步抽象训练。第二是复杂度意识。如果你直接按题意写递归小数据没问题数据稍微大一点就会出现大量重复计算。能不能意识到这一点、能不能拿出优化方案就是这门课和普通编程课的最大区别。第三是边界意识。n 1 时怎么办计数时要不要把数字本身算进去累加结果会不会溢出这些看上去细碎的问题恰恰是作业和考试扣分的重灾区。所以我不建议你只求一个能跑的答案而是把这道题当成一个完整的算法设计练习来做。2. 建立递推关系这道题最关键的一步2.1 手推 set(6)把直觉变成结构先把 set(6) 拆开看。6 本身算一个左侧加 1得到 16左侧加 2得到 26左侧加 3得到 36。到这里很多人就停了但 26 的左侧还能加不超过 1 的数于是得到 12636 的左侧也还能加不超过 1 的数得到 136。写成结构就是6 的左侧可以选择的前缀有 1、2、3 三种其中前缀 2 还能继续扩展出“12”这种前缀形态前缀 3 能扩展出“13”。换句话说左侧加上的那个前缀本身也有自己的“半数集”。所以 set(6) 的数量应该等于16 本身加上 set(1) 的规模加上 set(2) 的规模再加上 set(3) 的规模。这里要澄清一个容易绕晕的点这里的 set(i) 不是“数字 i 作为前缀时的个数”而是“以 i 为左侧前缀时能够继续向前扩展出的前缀形态数量”。用数学语言写出来就是f(n) 1 Σ f(i)其中 i 从 1 取到 ⌊n/2⌋边界条件 f(1) 1。f(1) 1 是因为 1 左边不能再加任何数不存在不超过 0.5 的自然数它只能以“1”本身这一种前缀形态出现。2.2 验证递推式的正确性光有公式还不够拿前几项手算一遍才能放心。我用这个递推关系从 f(1) 开始往下推n计算过程f(n)1边界121 f(1)231 f(1)241 f(1) f(2)451 f(1) f(2)461 f(1) f(2) f(3)671 f(1) f(2) f(3)681 f(1) f(2) f(3) f(4)10这个表也挺有意思f(2) 和 f(3) 相等f(4) 和 f(5) 相等f(6) 和 f(7) 相等。原因是奇数 n 和它前一个偶数 n-1 的 ⌊n/2⌋ 相同所以求和范围完全一样。但这种成对相等只是表象你要是敢根据“奇偶相同”直接推 f(n) f(n-1)遇到 n 为偶数时就会翻车。手算验证的价值就在这里它能让你提前发现规律也能让你规律总结得过早时撞上反例。3. 三种写法从朴素递归到高效递推3.1 最直观的递归实现先写一个完全照着题目翻译的版本。递归函数设计得很简单n 为 1 时返回 1否则先加上自己这一项然后枚举所有可能的左侧前缀把它们的 f 值累加进来。#include iostream using namespace std; long long f(int n) { if (n 1) return 1; long long ans 1; for (int i 1; i n / 2; i) { ans f(i); } return ans; } int main() { cout f(6) endl; // 输出 6 cout f(8) endl; // 输出 10 return 0; }代码没问题小数据也能跑出正确结果。但注意我函数返回值用了 long long而不是 int因为这道题虽然递推式简单累加规模上去以后数值会比你想的大得多int 很容易不够用。这是后话先记下。3.2 朴素递归为什么不能用于大规模数据如果拿这个版本去跑 n 100你会觉得还挺快跑 n 1000 就开始明显变慢。问题出在重复计算上以计算 f(6) 为例f(1) 会被调用很多次因为 f(4)、f(5)、f(6) 的循环里都要算 f(1)而 f(2) 又会被 f(4) 和 f(6) 重复调用。整个递归调用树长得非常快大量子树被反复展开。我在自己机器上实测过n 16 时函数 f 被调用了 36 次n 32 时变成 202 次n 64 时已经到 1828 次。这个增速很明显不是线性的而是随着 n 的增大不断加速。这就是“重叠子问题”的典型症状也是动态规划这门优化技术要解决的核心痛点。3.3 记忆化搜索把重复计算变成一次计算优化的思路很朴素算过的 f(i) 存下来下次用到直接查表。这就是记忆化搜索也叫备忘录法。改造后的代码几乎不动原始递归结构只是加了一个全局数组。const int MAXN 1005; long long memo[MAXN]; long long f(int n) { if (n 1) return 1; if (memo[n] ! 0) return memo[n]; long long ans 1; for (int i 1; i n / 2; i) { ans f(i); } return memo[n] ans; }这段代码最需要注意的地方是判重用memo[n] ! 0表示 f(n) 已经算过。因为半数集问题的答案永远大于等于 1所以用 0 做“未计算”标记是安全的。记忆化之后每个 f(i) 最多被真正计算一次时间复杂度从之前的疯涨状态降到了一个可控的二次级别。3.4 自底向上递推加前缀和最优版本记忆化虽然好用但循环内部仍在反复求和。如果细看递推式 f(n) 1 Σ f(i)你会发现求和部分其实可以维护一个前缀和数组把每次枚举的 O(n) 变成 O(1)。#include iostream #include vector using namespace std; long long f_dp(int n) { vectorlong long dp(n 1, 0), pre(n 1, 0); dp[1] 1; pre[1] 1; for (int i 2; i n; i) { dp[i] 1 pre[i / 2]; pre[i] pre[i - 1] dp[i]; } return dp[n]; } int main() { cout f_dp(6) endl; // 6 cout f_dp(100) endl; // 远大于 2验证用 return 0; }这个版本的时间复杂度就是严格的 O(n)空间复杂度 O(n)。递推从 2 到 n 一路算上去每一轮只做一次查表和一次累加没有任何多余的枚举操作。三种写法放在一起对比学习价值就很明显了实现方案时间复杂度空间复杂度适用场景朴素递归增长快不可用于大 nO(log n) 递归栈理解递归结构记忆化搜索O(n²)O(n)n 在几千以内思路直白递推 前缀和O(n)O(n)大规模数据最优解4. 复杂度分析的完整推演过程4.1 暴力递归的调用次数到底涨多快很多同学能写递归但说不清楚它为什么慢。这里给出一个严谨的推演设 C(n) 表示计算 f(n) 时函数 f 被调用的总次数包括第一次调用自身。根据代码结构可以直接写出C(1) 1C(n) 1 Σ C(i)其中 i 从 1 取到 ⌊n/2⌋。这个方程乍一看和 f(n) 自己的递推长得一样但含义不同它统计的是“次数”而不是“数值”。为了看清增长趋势可以相邻项做差。当 n 为偶数时观察 C(2k) 和 C(2k-1)C(2k) 1 Σ_{i1}^{k} C(i)C(2k-1) 1 Σ_{i1}^{k-1} C(i)两式相减得到 C(2k) - C(2k-1) C(k)。这个结果很有意思偶数位置的调用次数增量恰好等于一半位置的调用次数。这说明调用次数不是简单的线性增长而是把之前一半规模的数据“叠加”进来越往后增量越显著。虽然可以证明它的上界不超过指数级别但从实测数据看n 翻一倍调用次数会扩大好几倍这种增速对实际运行来说已经非常不友好了。4.2 记忆化之后为什么变成 O(n²)记忆化搜索之所以快是因为每个 f(i) 都只真正计算一次。但注意计算 f(i) 的时候内部还有一个循环要枚举 j 1 到 i/2做 i/2 次加法。把所有 i 的循环工作量加起来Σ(i/2) ≈ n²/4所以记忆化搜索的完整时间复杂度是 O(n²)空间 O(n)。这里经常有人误以为记忆化就是 O(n)只看到了状态数忽略了每个状态内部的枚举成本。考试时如果只答“每个子问题算一次所以是 O(n)”是要被扣分的。4.3 前缀和优化为什么能到 O(n)前缀和版本的优化点在于把每个状态内部的枚举去掉。观察递推式 f(i) 1 pre(i/2)其中 pre(k) Σ_{j1}^{k} f(j)。因为 pre 数组在递推过程中同步维护每次查询 pre(i/2) 都是 O(1)所以总时间就是状态数 n 乘上单次 O(1)即 O(n)。这其实给了我们一个通用启发很多形如 f(n) 某常数 前缀和形式的递推都可以用这个技巧压掉内层循环。以后再遇到类似的递推计数题可以先观察求和部分是不是连续前缀是的话就果断上前缀和数组。4.4 顺嘴说一句主定理的适用范围这道题也常被拿来练“递推方程求解”但写作业时别硬套主定理。主定理处理的是 T(n) aT(n/b) f(n) 这种标准分治形态也就是递归调用只针对 n/b 这样的等比缩小子问题。半数集问题的递推是“对 1 到 n/2 的所有子区间求和”形态完全不一样套主定理会得出错误结论。正确的做法是像上面那样单独分析求和递归或者干脆理解成动态规划的状态转移方程。这个分辨能力本身就是算法设计与分析的重点考察内容。5. 常见错误与考场排查实录5.1 错误一忘记给数字本身计数最经典的低级错误是把递推写成 return 1 sum 时漏掉前面那个 1或者把累加初始值写成 0。比如有人会写long long f(int n) { if (n 1) return 0; // 错f(1) 应该是 1 long long ans 0; // 错至少要把自身算进去 for (int i 1; i n / 2; i) ans f(i); return ans; }这样算 f(4) 会得到 f(1) f(2) 0 2 2正确答案是 4直接就差了一大截。排查方法很简单拿到题先手算 f(1) 到 f(5)再拿程序输出对比。如果从小数据就开始对不上十有八九是边界或者计数项写错了。5.2 错误二只允许加一次前缀把 set(6) 算成 {6, 16, 26, 36} 共 4 个是理解层面的错误。它的本质是把“半数集”理解成了“半数前缀”忽略了新生成的 26、36 还能继续向左扩展。这种错误写进递推式就会变成 f(n) 1 ⌊n/2⌋完全偏离了题目本意。我在批改作业时见过不少次而且这类错误最难通过样例发现因为 n 4 时 f(4) 1 2 3正确答案也是 3小数据根本暴露不出来。建议多测几个非对称的用例比如 n 6、n 8很容易就把两种理解的差异拉开。5.3 错误三数值溢出和边界不处理半数集的 f(n) 不是那种瞬间爆炸的增长但 n 到几百上千之后结果还是会超过 int 范围。我测试过n 100 时的 f(100) 已经不小直接开 long long 是最稳妥的。另一个边界是 n 0多数教材定义的是自然数 n 且作为参数传入时 n ≥ 1但如果你的函数支持 n 0记得单独讨论否则 n 1 时循环里调用 f(0) 就会出错。5.4 错误四作业提交超时却不知道问题在哪如果你把朴素递归交上去评测系统大概率会超时。遇到这种问题别急着改代码先做一件事加一个计数器统计 f 函数的调用次数。代码只需要在函数入口处执行cnt跑几个 n 值打印调用次数你就能非常直观地看到重复计算有多严重。这也是一个通用排查技巧任何递归超时问题第一步永远是量化递归调用次数而不是盲目换写法。6. 半数集问题的变形与迁移价值6.1 变形一半数单集有些教材会把题目改成“求半数单集”要求生成的所有数字互不相同但允许同一个数字通过不同的加前缀路径产生时只算一次。这个问题会在递归过程中出现重复元素直接套前面的递推式会多算。解决办法通常是加一个去重集合或者在递推式里减去重复贡献。它比原题多一个维度适合作为进阶练习。6.2 变形二从计数改成枚举输出如果题目要求输出的不是数量而是把 set(n) 的所有元素全部打印出来那就不能只用递推计数了要改成递归枚举加回溯。思路依然是以 n 为根枚举左侧前缀 i然后递归处理“前缀 i 的前缀”。枚举版本的复杂度会显著上升因为输出本身就可能是指数规模的这时候计数递推只能作为验证手段不能替代真正的构造过程。6.3 从这道题抽象出的通用解题模板回过头来看半数集问题实际上提供了一个对付递推计数题的万能框架一共四步。第一步定义清楚状态代表的含义第二步手算小数据找结构第三步写出递推方程并验证前三项第四步分析复杂度后决定要不要优化。很多看起来吓人的计数题比如整数划分、括号序列数量、满二叉树个数走完这四步都会变得清晰很多。最后说点个人体会。我当年第一次做这道题写的就是漏掉“1”的版本拿 f(4) 怎么验都不对后来手动展开 n 6 才意识到原来每个数字自身也要被计数。从那次之后凡是遇到递推计数题我都会强制自己先手算前三项再写代码这个习惯帮我至少拦住了五次作业里的低级错误。如果你也在学算法设计与分析强烈建议把这道题当成一个微型训练场能独立完成建模、实现、优化、验证四步递归与分治这一章你就已经拿到一半以上的分了。