1. 从一道经典题目认识递推与递归第一次看到《数的计数》这道题时我完全被题目描述绕晕了。题目大意是说给定一个正整数n我们可以在这个数的左边添加不超过它一半的数字重复这个过程直到不能添加为止问总共有多少种不同的生成方式。比如n6时可以生成6、16、26、36、126、136这六种序列。这道题出现在NOIP2001普及组至今仍是算法竞赛入门的经典例题。它完美展现了递推和递归这两种基础算法思想的应用场景。我记得当初自己尝试暴力枚举所有可能性结果当n超过20时程序就跑不动了。后来才明白这类问题必须找到其中的数学规律。初学者常犯的错误是试图用深度优先搜索(DFS)暴力解决。比如对于n6可能会画出这样的递归树从6出发可以添加1、2、3因为⌊6/2⌋3然后对每个添加的数字继续递归。这种方法在n较小时可行但当n达到1000时时间复杂度会呈指数级增长。2. 递推解法像搭积木一样构建解2.1 递推的三要素解决这类计数问题递推是最自然的思路。我们需要明确三个关键要素状态定义设a[i]表示数字i能生成的所有序列数量初始状态a[0]1表示不添加数字的空序列递推关系a[i] sum(a[j])其中j从0到⌊i/2⌋这个关系怎么理解呢以i6为例可以在6后面添加0即不添加对应a[0]可以添加1对应a[1]可以添加2对应a[2]可以添加3对应a[3] 所以a[6]a[0]a[1]a[2]a[3]2.2 递推的实现细节用代码实现这个思路非常直观。我们先初始化一个数组a然后按从小到大的顺序填充int a[1005] {0}; // 初始化数组 a[0] 1; // 初始状态 for(int i1; in; i) { for(int j0; ji/2; j) { a[i] a[j]; // 累加所有可能的前驱状态 } } cout a[n]; // 输出结果这个解法的时间复杂度是O(n²)对于n≤1000完全够用。我在本地测试时n1000的运行时间不到1毫秒相比暴力搜索简直是天壤之别。3. 记忆化递归给递归装上备忘录3.1 递归的直观理解有些同学可能觉得递推的思路不太直观更喜欢递归的思考方式。我们可以这样定义递归函数getNum(n)返回数字n能生成的所有序列数量递归关系getNum(n) sum(getNum(j)), j∈[0, ⌊n/2⌋]递归出口getNum(0) 1这种思路虽然直观但直接实现会有严重的重复计算问题。比如计算getNum(6)时需要计算getNum(3)而计算getNum(4)时又需要计算getNum(3)这就造成了重复计算。3.2 记忆化优化这时候就需要引入记忆化技术。我们用一个数组num来记录已经计算过的结果int num[1005] {0}; // 记忆化数组 int getNum(int k) { if(k 0) return 1; if(num[k] 0) return num[k]; // 已经计算过直接返回 int sum 0; for(int j0; jk/2; j) { sum getNum(j); } return num[k] sum; // 保存计算结果 }记忆化递归的时间复杂度也是O(n²)但因为递归调用的开销实际运行时间会比递推稍长。不过它的优势在于思维更符合问题本身的定义更容易理解和调试。4. 递推关系的优化技巧4.1 发现隐藏规律仔细观察递推公式我们可以发现一个优化点。比较a[i]和a[i-1]的关系当i为偶数时a[i] a[i-1] a[i/2]当i为奇数时a[i] a[i-1]这个规律可以通过数学归纳法证明。以i6为例 a[6] a[0]a[1]a[2]a[3] a[5] a[0]a[1]a[2] 而a[3] a[0]a[1] a[2] 所以a[6] a[5] a[3] a[5] a[3]4.2 优化后的实现利用这个规律我们可以将时间复杂度优化到O(n)a[0] 1; for(int i1; in; i) { if(i % 2 0) { a[i] a[i-1] a[i/2]; } else { a[i] a[i-1]; } }这个优化让代码更加简洁高效。在实际比赛中这种观察递推关系隐藏规律的能力非常重要往往能带来显著的性能提升。5. 算法选择与实战建议5.1 递推 vs 记忆化递归两种方法各有优劣递推通常更快适合线性问题记忆化递归思维更直观适合树状结构的问题在竞赛中我建议优先考虑递推解法。它不仅效率高而且代码通常更简洁。但当问题有明显的递归结构时记忆化递归可能是更好的选择。5.2 调试技巧在实现这类算法时有几个调试技巧很实用先手动计算小规模的n验证程序输出打印中间结果比如计算过程中的a数组对于递归解法可以添加日志输出观察递归调用过程记得我第一次做这道题时因为忘记初始化a[0]1导致所有结果都错了。这种基础错误在竞赛中很常见需要特别注意。6. 举一反三类似问题解析《数的计数》这类问题在算法竞赛中很常见。比如爬楼梯问题每次可以走1步或2步问有多少种走法硬币找零用给定面额的硬币凑出指定金额的组合数括号生成生成所有有效的括号组合这些问题都可以用类似的递推或记忆化递归思路解决。掌握这类问题的解题模式对提升算法能力很有帮助。在实际训练中我推荐到洛谷等OJ平台多练习同类题目。比如P1192 台阶问题P1025 数的划分P1044 栈这些题目都能帮助你巩固递推和递归的解题技巧。