1. 项目概述从“地盘划分”理解算法竞赛的思维基石最近在辅导一些准备参加CCF CSP-J/S认证的中小学生时我发现很多孩子对“递推”和“递归”这两个核心算法思想感到困惑。他们能背出定义但一到具体问题比如经典的“地盘划分”问题就不知道如何下手该用递推还是递归脑子里一团乱麻。这让我想起自己当年刚开始接触信息学竞赛时的样子面对一个看似简单的题目却总觉得无从建模。今天我就以“C地盘划分”这个极具代表性的问题为引子把递推和递归这两种算法的实现思路、代码细节以及背后的思维逻辑掰开揉碎了讲清楚。这不仅是解一道题更是帮你建立解决一大类“计数”或“划分”问题的通用思维框架。无论你是正在备战CSP-J/S的选手还是希望夯实C算法基础的初学者相信这篇结合了实战代码和深度思考的分享都能让你对“如何用程序思维解决问题”有更透彻的理解。“地盘划分”问题通常抽象为将一个整数n代表长度、面积或某种资源总量划分成若干份求不同的划分方法数。它直接考察的是对问题状态的抽象能力和对递推关系的发现能力。在CSP-J乃至更高级别的竞赛中这类问题频繁出现因为它完美地串联了循环、数组、函数、递归等基础语法以及动态规划、搜索等核心算法思想的雏形。理解它你就握住了打开算法世界大门的一把关键钥匙。2. 问题定义与核心思路拆解2.1 “地盘划分”问题的经典模型我们首先需要把问题具体化。一个最经典的“地盘划分”模型是将一个正整数n划分成若干个正整数之和求划分的总数不考虑顺序。例如n4时431222111111 所以总共有5种划分方法。在竞赛中题目往往会加上一些限制条件让问题变得更加丰富例如划分成若干正整数之和即上述经典问题记作P(n)。划分成不超过m的整数之和记作P(n, m)。例如将4划分成不超过2的整数之和那么“31”就不合法因为32。划分成恰好k个正整数之和。划分成互不相同的正整数之和。我们今天重点讨论前两种因为它们最能体现递推和递归思想的本质区别与联系。解决这个问题的核心在于我们如何定义“状态”以及如何找到不同状态之间的“关系”。2.2 递推与递归的思维分野这是很多初学者最迷糊的地方。我用一个简单的比喻来解释递推Iteration/Dynamic Programming像盖房子。你从地基最简单的情况比如n1开始一层一层、有条不紊地往上盖。你知道每一层砖状态P(i)都需要依赖下面几层砖状态P(i-1), P(i-2)等来垒砌。你的思维是自底向上的视野是全局的目标是最终建成整栋大楼求出P(n)。这个过程通常用循环来实现。递归Recursion像拆礼物盒。一个大盒子问题P(n)里面可能套着小盒子子问题P(n-1), P(n-2)等。你的策略是直接打开这个大盒子如果发现里面还有盒子就继续打开直到找到最小的、一眼就能知道里面是什么的盒子基础情况如n0或1。你的思维是自顶向下的是“分而治之”的目标是把大问题不断分解成小问题。这个过程用函数调用自身来实现。对于“地盘划分”问题递推的优点是效率高无重复计算但需要你想清楚状态转移方程递归的优点是思路直观符合人的自然思维但可能效率低下存在大量重复计算。在CSP-J中由于数据规模通常不大n 50或100两种方法都可能通过。但理解递推是为将来学习动态规划DP打下坚实基础而掌握递归则是理解深度优先搜索DFS等算法的前提。3. 递推算法实现详解我们以“将n划分成不超过m的整数之和”为例讲解递推解法。定义状态dp[n][m]为将整数n划分成不超过m的整数之和的方法数。3.1 状态定义与转移方程推导关键在于寻找dp[n][m]与更小状态之间的关系。我们考虑划分中是否包含整数m这个边界值划分中不包含m那么所有的加数都小于等于m-1。这正好就是状态dp[n][m-1]的定义。划分中包含至少一个m那么我们可以先拿出一个m剩下的总和是 n-m并且剩下的部分仍然可以包含m因为允许重复。这正好就是状态dp[n-m][m]的定义。因此我们得到了核心的状态转移方程dp[n][m] dp[n][m-1] dp[n-m][m]当然这个方程成立需要一些前提条件边界情况当n m时不可能包含m所以dp[n][m] dp[n][n]。实际上此时dp[n][m] dp[n][n]因为最大加数不可能超过n本身。当m 1时只有一种划分法全是1。所以dp[n][1] 1。当n 0时我们认为有一种划分法什么都不取空划分。所以dp[0][m] 1。这是递推的起点非常重要。当n 0时为非法情况值为0。基于以上分析我们可以用一张二维表来逐步填充最终dp[n][n]就是我们要求的经典划分总数P(n)。3.2 C代码实现与逐行解析下面是用递推动态规划实现的C代码。为了节省空间我们可以使用滚动数组优化但为了清晰理解这里先展示完整的二维DP表。#include iostream #include vector using namespace std; int countPartitionsDP(int n) { if (n 0) return 0; // 创建DP表大小为 (n1) x (n1)初始化为0 vectorvectorlong long dp(n 1, vectorlong long(n 1, 0)); // 初始化边界条件 for (int i 0; i n; i) { dp[0][i] 1; // 总和为0只有一种划分空 } for (int i 1; i n; i) { dp[i][1] 1; // 最大加数为1只有全1这一种划分 } // 核心递推过程 for (int i 1; i n; i) { // i 代表当前要划分的总和 for (int j 2; j n; j) { // j 代表当前允许的最大加数 if (j i) { // 如果允许的最大加数j超过了当前总和i那么最大加数实际只能是i dp[i][j] dp[i][i]; } else { // 状态转移方程: dp[i][j] dp[i][j-1] dp[i-j][j] dp[i][j] dp[i][j-1] dp[i-j][j]; } } } // 最终结果将n划分成不超过n的整数之和即P(n) return dp[n][n]; } int main() { int n; cout 请输入一个正整数 n: ; cin n; int result countPartitionsDP(n); cout 整数 n 的划分数为: result endl; // 附加输出不超过m的划分例如m3 int m 3; if (n m) { // 注意我们的dp表已经计算好了所有dp[i][j] cout 整数 n 划分成不超过 m 的整数之和的方法数为: dp[n][m] endl; } return 0; }代码关键点解析数据类型划分数可能增长很快n50时结果已经很大所以使用long long是更安全的选择避免整数溢出。DP表初始化dp[0][i] 1是递推的“基石”。可以理解为总和为0时只有一种方式——什么都不选。这个初始化保证了后续递推的正确性。递推顺序外层循环i从1到n内层循环j从2到n。这个顺序保证了在计算dp[i][j]时它所依赖的状态dp[i][j-1]和dp[i-j][j]都已经被计算出来了。这是动态规划能正确运行的关键。条件判断if (j i)这是对状态转移方程的修正。当允许的最大加数j大于当前总和i时划分中不可能出现j因此问题退化为dp[i][i]。实操心得在写递推/动态规划代码时我习惯先手动画一个小的DP表比如n5然后手动模拟填充过程。这能帮你直观地理解状态转移和循环顺序是调试和验证逻辑的最有效方法。很多思路上的卡壳画个表就通了。3.3 空间优化滚动数组技巧上面的代码空间复杂度是O(n²)。当n很大时比如n1000这可能成为瓶颈。观察状态转移方程dp[i][j] dp[i][j-1] dp[i-j][j]我们发现计算第i行时只依赖于本行的前一列j-1和上一行的某一列i-j。因此我们可以优化为一维数组。int countPartitionsDP_Optimized(int n) { if (n 0) return 0; vectorlong long dp(n 1, 0); dp[0] 1; // 基础情况 // 核心递推此时外层循环是“最大加数”m内层循环是“总和”i for (int m 1; m n; m) { for (int i m; i n; i) { // dp[i] 表示将i划分成不超过当前m的整数之和的方法数 // 更新前dp[i]保存的是“不超过m-1”的划分数 // 更新后dp[i]需要加上“包含至少一个m”的划分数即dp[i-m] dp[i] dp[i - m]; } } return dp[n]; }优化版解析这个版本的理解角度稍有不同。外层循环的m可以看作是“当前考虑使用的最大硬币面值”内层循环的i是“要凑成的总金额”。dp[i]表示用面值不超过m的硬币凑成金额i的方法数。当m从1遍历到n时我们逐渐将更大的“加数”纳入考虑范围。对于每个idp[i] dp[i-m]的含义是在已有方案使用不超过m-1的加数的基础上加上那些以至少一个m开头的方案。而这些方案的数量正好等于凑成i-m剩下的部分且允许使用m的方案数即当前的dp[i-m]。这个版本代码更简洁效率更高是竞赛中的常用写法。但它背后的思维转换需要时间理解。我建议先彻底掌握二维DP的版本再来看这个一维优化你会对“状态压缩”有更深的认识。4. 递归算法实现与深度分析递归解法更符合人类最直接的思考方式要计算P(n, m)将n划分成不超过m的整数之和我就直接考虑两种情况划分里没有m以及划分里至少有一个m。4.1 递归函数设计与终止条件我们设计递归函数int partition(int n, int m)。函数语义返回将整数n划分成不超过m的正整数之和的方法数。递归关系递推关系情况1划分中不包含m。那么方法数等于partition(n, m-1)。情况2划分中至少包含一个m。那么我们可以先放一个m剩下的n-m继续划分且仍然可以包含m。方法数等于partition(n-m, m)。所以partition(n, m) partition(n, m-1) partition(n-m, m)。看这和我们的递推方程一模一样终止条件递归基如果n 0说明我们已经成功分配完找到一种划分返回1。如果m 0或n 0说明当前路径无效返回0。如果m n那么最大加数m实际上用不上问题等价于partition(n, n)。4.2 C递归代码实现#include iostream using namespace std; // 递归函数计算将n划分成不超过m的正整数之和的方法数 long long partitionRecur(int n, int m) { // 终止条件 if (n 0) return 1; // 找到一种有效的划分 if (m 0 || n 0) return 0; // 无效的路径 if (m n) return partitionRecur(n, n); // 最大加数超过总和等价于partition(n, n) // 递归关系两种情况 // 1. 划分中不包含m方法数 partitionRecur(n, m-1) // 2. 划分中包含至少一个m方法数 partitionRecur(n-m, m) return partitionRecur(n, m-1) partitionRecur(n-m, m); } int main() { int n; cout 请输入一个正整数 n: ; cin n; long long result partitionRecur(n, n); cout 整数 n 的划分数为递归: result endl; return 0; }这段代码非常简洁几乎就是数学定义的直接翻译。输入n4它会展开一棵递归调用树来计算结果。4.3 递归的陷阱重复计算与性能危机虽然递归代码简洁易懂但它有一个致命的缺点大量的重复计算。我们以计算partition(5, 3)为例画出部分递归树partition(5,3) partition(5,2) partition(2,3) [partition(5,1) partition(3,2)] [partition(2,2) partition(-1,3)] ...你会发现像partition(3,2)、partition(2,2)这样的子问题会被不同的父问题多次计算。当n增大到30或40时这棵递归树会变得异常庞大导致程序运行时间呈指数级增长最终超时。踩坑实录我初学递归时曾用这种方法计算n30的划分数程序跑了十几秒都没出结果。这就是典型的“指数爆炸”问题。在算法竞赛中CSP-J的题目时间限制通常是1秒纯递归解法对于n30的数据基本都会超时。4.4 递归的救星记忆化搜索如何保留递归的直观性又避免重复计算答案是记忆化搜索Memoization。其核心思想是“用空间换时间”我们用一个缓存通常是一个二维数组来记录已经计算过的子问题的结果。在递归函数开始时先检查缓存中是否有答案如果有直接返回如果没有才进行计算并将结果存入缓存后再返回。#include iostream #include vector using namespace std; // 记忆化搜索版本 long long partitionMemo(int n, int m, vectorvectorlong long memo) { // 先查表 if (memo[n][m] ! -1) { return memo[n][m]; } // 终止条件 if (n 0) return memo[n][m] 1; if (m 0 || n 0) return 0; // 注意n0的情况在调用前判断更好 if (m n) { memo[n][m] partitionMemo(n, n, memo); return memo[n][m]; } // 递归计算并保存结果 long long res partitionMemo(n, m-1, memo) partitionMemo(n-m, m, memo); memo[n][m] res; return res; } long long countPartitionsMemo(int n) { if (n 0) return 0; // 初始化备忘录-1表示未计算 vectorvectorlong long memo(n 1, vectorlong long(n 1, -1)); return partitionMemo(n, n, memo); } int main() { int n; cout 请输入一个正整数 n: ; cin n; long long result countPartitionsMemo(n); cout 整数 n 的划分数为记忆化搜索: result endl; return 0; }记忆化搜索的精髓memo数组的大小是(n1) x (n1)初始化为-1或任何不会出现的值表示该状态未被计算。在递归函数partitionMemo的开头首先检查memo[n][m]。如果不是-1直接返回避免了重复的递归调用。在返回结果前将计算结果存入memo[n][m]。经过记忆化优化后每个状态(n, m)最多只被计算一次时间复杂度从指数级降到了O(n²)和递推的动态规划完全一样而它的代码结构依然保持着递归的清晰逻辑。核心技巧记忆化搜索是连接递归思维和高效算法的一座桥梁。当你面对一个复杂问题能写出递归解法但担心超时时第一个应该想到的优化手段就是记忆化。它让你既能享受递归“分治”思路的清晰又能获得接近动态规划的效率。5. 递推与递归的对比与选型指南通过上面的详细实现我们可以对两种方法做一个全面的比较特性维度递推动态规划递归记忆化前递归记忆化后思维方式自底向上从基础情况构建自顶向下分解问题自顶向下分解问题代码结构循环嵌套结构清晰函数自我调用简洁直观函数自我调用缓存检查时间复杂度O(n²)O(指数级)极慢O(n²)与递推相同空间复杂度O(n²) 或优化为 O(n)O(n)调用栈深度O(n²)缓存表 O(n)调用栈优点效率高无函数调用开销思路直接易于理解和实现兼具递归的清晰和DP的效率缺点状态转移方程不易想存在大量重复计算n稍大即超时递归调用仍有栈溢出风险n极大时适用场景竞赛主流处理大规模数据仅用于理解思路或极小规模数据当递推顺序难以确定时用记忆化搜索更自然给CSP-J选手的实战建议优先掌握递推/动态规划这是竞赛中的绝对主力。对于“地盘划分”这类经典计数问题要训练自己快速定义状态dp[i][j]代表什么和推导转移方程的能力。递归作为思考工具在纸上分析问题时先用递归的思路去拆分问题想清楚递归关系和终止条件。这能帮你理清逻辑。一旦思路清晰尝试将其转化为递推形式。记忆化搜索是“保底”利器如果比赛时时间紧张或者递推的顺序非常别扭比如某些依赖关系不是简单的从左到右、从上到下那么果断写一个记忆化搜索的递归。它几乎总能保证你得到正确的分数虽然可能不是最优解但远比写不出来的递推或超时的纯递归要好。注意数据范围和溢出像划分数这种问题结果增长很快。务必使用long long甚至高精度来计算和存储结果。在CSP-J中仔细阅读题目中的数据规模约定和结果取模要求如果有的话。6. 举一反三常见变式问题解析掌握了基本模型我们来看看“地盘划分”问题在竞赛中可能出现的几种变式以及如何调整我们的算法。6.1 变式一划分成恰好k个正整数之和定义状态dp[n][k]为将n划分成恰好k个正整数之和的方法数。思考如何转移 我们可以考虑最后一个数第k个数是多少。假设它是x(x 1)那么前k-1个数的和就是n-x并且这k-1个数每个都至少是1。这就将问题转化为了一个子问题。但更巧妙的思路是dp[n][k] dp[n-k][k] dp[n-1][k-1]dp[n-k][k]对应所有划分中每个数都至少为2的情况。我们可以给每个数先减去1总和就变成了n-k但仍然有k个数。dp[n-1][k-1]对应划分中包含至少一个1的情况。我们把这个1拿出来剩下的n-1划分成k-1个数。 这个方程需要仔细理解是动态规划中一种常见的“通过变换保证状态一致性”的技巧。6.2 变式二划分成互不相同的正整数之和这就是整数拆分的另一种形式。定义状态dp[n][m]为将n划分成不超过m的互不相同的正整数之和的方法数。 状态转移需要考虑“不重复”这个限制dp[n][m] dp[n][m-1] dp[n-m][m-1]dp[n][m-1]划分中不包含m。dp[n-m][m-1]划分中包含m。因为要求互不相同既然已经用了一个m剩下的数就不能再超过m-1。6.3 变式三输出具体的划分方案有时题目不仅要求数量还要求输出所有具体的划分方案。这就不能用动态规划了必须使用深度优先搜索DFS其本质就是递归枚举所有可能性。#include iostream #include vector using namespace std; vectorint current; // 存储当前划分方案 // DFS函数寻找将remain划分成不超过max_num的整数之和的所有方案 void dfs(int remain, int max_num) { if (remain 0) { // 找到一种方案输出 for (int i 0; i current.size(); i) { cout current[i]; if (i ! current.size() - 1) cout ; } cout endl; return; } // 从大到小尝试避免重复如31和13被视为相同 // 也可以从小到大但需要额外机制去重 for (int num min(remain, max_num); num 1; --num) { current.push_back(num); // 选择num dfs(remain - num, num); // 剩余部分最大加数不能超过num保证非递增从而去重 current.pop_back(); // 回溯撤销选择 } } int main() { int n; cout 请输入n将输出所有划分方案: ; cin n; current.clear(); dfs(n, n); // 初始时最大加数可以是n return 0; }这个DFS代码通过限制下一次选择的最大数不超过当前选择的数dfs(remain - num, num)保证了输出的划分是非递增的从而自动避免了顺序不同导致的重复方案如31和13。这是输出具体方案时一个非常重要的去重技巧。7. 从“地盘划分”到CSP-J算法学习路径“地盘划分”问题就像一颗种子从中可以生长出算法学习的整棵大树。对于CSP-J的选手我建议按照以下路径以点带面地进行学习基础语法巩固阶段通过实现递推和递归彻底掌握C的循环、数组、函数和递归调用。这是所有算法的基础。递推与简单动态规划将“地盘划分”的递推思想扩展到其他问题如斐波那契数列、爬楼梯、杨辉三角、最大子段和等。理解“状态”和“转移”的概念。深度优先搜索DFS从输出划分方案的DFS代码出发学习回溯法。尝试解决全排列、组合、子集、迷宫路径等问题。这是暴力搜索和优化搜索的基础。记忆化搜索深刻理解记忆化如何将指数级复杂度的递归优化为多项式复杂度。尝试解决经典的“滑雪”、“数字三角形”等问题。正式动态规划当你对记忆化搜索得心应手后动态规划的状态设计和方程推导就会变得自然。这时可以挑战背包问题01背包、完全背包、区间DP、树形DP等更复杂的模型。学习过程中切忌只刷题不总结。每做完一道题尤其是像“地盘划分”这样的经典问题要问自己几个问题这道题的核心模型是什么状态如何定义转移方程为什么这样写有没有更优的解法和之前做过的哪类题相似建立这样的知识关联你的算法能力才能扎实地增长。最后关于工具很多同学问VSCode配置C环境的问题。我的建议是在初学阶段一个简单可靠的IDE如Dev-C、Code::Blocks比VSCode更省心。等到你开始做规模稍大的项目或需要更强大的调试功能时再花时间研究VSCodeMinGW的配置。竞赛备考稳定和熟悉比“高大上”更重要。把时间花在算法思维训练上远比折腾环境带来的收益大得多。
1. 项目概述从“地盘划分”理解算法竞赛的思维基石最近在辅导一些准备参加CCF CSP-J/S认证的中小学生时我发现很多孩子对“递推”和“递归”这两个核心算法思想感到困惑。他们能背出定义但一到具体问题比如经典的“地盘划分”问题就不知道如何下手该用递推还是递归脑子里一团乱麻。这让我想起自己当年刚开始接触信息学竞赛时的样子面对一个看似简单的题目却总觉得无从建模。今天我就以“C地盘划分”这个极具代表性的问题为引子把递推和递归这两种算法的实现思路、代码细节以及背后的思维逻辑掰开揉碎了讲清楚。这不仅是解一道题更是帮你建立解决一大类“计数”或“划分”问题的通用思维框架。无论你是正在备战CSP-J/S的选手还是希望夯实C算法基础的初学者相信这篇结合了实战代码和深度思考的分享都能让你对“如何用程序思维解决问题”有更透彻的理解。“地盘划分”问题通常抽象为将一个整数n代表长度、面积或某种资源总量划分成若干份求不同的划分方法数。它直接考察的是对问题状态的抽象能力和对递推关系的发现能力。在CSP-J乃至更高级别的竞赛中这类问题频繁出现因为它完美地串联了循环、数组、函数、递归等基础语法以及动态规划、搜索等核心算法思想的雏形。理解它你就握住了打开算法世界大门的一把关键钥匙。2. 问题定义与核心思路拆解2.1 “地盘划分”问题的经典模型我们首先需要把问题具体化。一个最经典的“地盘划分”模型是将一个正整数n划分成若干个正整数之和求划分的总数不考虑顺序。例如n4时431222111111 所以总共有5种划分方法。在竞赛中题目往往会加上一些限制条件让问题变得更加丰富例如划分成若干正整数之和即上述经典问题记作P(n)。划分成不超过m的整数之和记作P(n, m)。例如将4划分成不超过2的整数之和那么“31”就不合法因为32。划分成恰好k个正整数之和。划分成互不相同的正整数之和。我们今天重点讨论前两种因为它们最能体现递推和递归思想的本质区别与联系。解决这个问题的核心在于我们如何定义“状态”以及如何找到不同状态之间的“关系”。2.2 递推与递归的思维分野这是很多初学者最迷糊的地方。我用一个简单的比喻来解释递推Iteration/Dynamic Programming像盖房子。你从地基最简单的情况比如n1开始一层一层、有条不紊地往上盖。你知道每一层砖状态P(i)都需要依赖下面几层砖状态P(i-1), P(i-2)等来垒砌。你的思维是自底向上的视野是全局的目标是最终建成整栋大楼求出P(n)。这个过程通常用循环来实现。递归Recursion像拆礼物盒。一个大盒子问题P(n)里面可能套着小盒子子问题P(n-1), P(n-2)等。你的策略是直接打开这个大盒子如果发现里面还有盒子就继续打开直到找到最小的、一眼就能知道里面是什么的盒子基础情况如n0或1。你的思维是自顶向下的是“分而治之”的目标是把大问题不断分解成小问题。这个过程用函数调用自身来实现。对于“地盘划分”问题递推的优点是效率高无重复计算但需要你想清楚状态转移方程递归的优点是思路直观符合人的自然思维但可能效率低下存在大量重复计算。在CSP-J中由于数据规模通常不大n 50或100两种方法都可能通过。但理解递推是为将来学习动态规划DP打下坚实基础而掌握递归则是理解深度优先搜索DFS等算法的前提。3. 递推算法实现详解我们以“将n划分成不超过m的整数之和”为例讲解递推解法。定义状态dp[n][m]为将整数n划分成不超过m的整数之和的方法数。3.1 状态定义与转移方程推导关键在于寻找dp[n][m]与更小状态之间的关系。我们考虑划分中是否包含整数m这个边界值划分中不包含m那么所有的加数都小于等于m-1。这正好就是状态dp[n][m-1]的定义。划分中包含至少一个m那么我们可以先拿出一个m剩下的总和是 n-m并且剩下的部分仍然可以包含m因为允许重复。这正好就是状态dp[n-m][m]的定义。因此我们得到了核心的状态转移方程dp[n][m] dp[n][m-1] dp[n-m][m]当然这个方程成立需要一些前提条件边界情况当n m时不可能包含m所以dp[n][m] dp[n][n]。实际上此时dp[n][m] dp[n][n]因为最大加数不可能超过n本身。当m 1时只有一种划分法全是1。所以dp[n][1] 1。当n 0时我们认为有一种划分法什么都不取空划分。所以dp[0][m] 1。这是递推的起点非常重要。当n 0时为非法情况值为0。基于以上分析我们可以用一张二维表来逐步填充最终dp[n][n]就是我们要求的经典划分总数P(n)。3.2 C代码实现与逐行解析下面是用递推动态规划实现的C代码。为了节省空间我们可以使用滚动数组优化但为了清晰理解这里先展示完整的二维DP表。#include iostream #include vector using namespace std; int countPartitionsDP(int n) { if (n 0) return 0; // 创建DP表大小为 (n1) x (n1)初始化为0 vectorvectorlong long dp(n 1, vectorlong long(n 1, 0)); // 初始化边界条件 for (int i 0; i n; i) { dp[0][i] 1; // 总和为0只有一种划分空 } for (int i 1; i n; i) { dp[i][1] 1; // 最大加数为1只有全1这一种划分 } // 核心递推过程 for (int i 1; i n; i) { // i 代表当前要划分的总和 for (int j 2; j n; j) { // j 代表当前允许的最大加数 if (j i) { // 如果允许的最大加数j超过了当前总和i那么最大加数实际只能是i dp[i][j] dp[i][i]; } else { // 状态转移方程: dp[i][j] dp[i][j-1] dp[i-j][j] dp[i][j] dp[i][j-1] dp[i-j][j]; } } } // 最终结果将n划分成不超过n的整数之和即P(n) return dp[n][n]; } int main() { int n; cout 请输入一个正整数 n: ; cin n; int result countPartitionsDP(n); cout 整数 n 的划分数为: result endl; // 附加输出不超过m的划分例如m3 int m 3; if (n m) { // 注意我们的dp表已经计算好了所有dp[i][j] cout 整数 n 划分成不超过 m 的整数之和的方法数为: dp[n][m] endl; } return 0; }代码关键点解析数据类型划分数可能增长很快n50时结果已经很大所以使用long long是更安全的选择避免整数溢出。DP表初始化dp[0][i] 1是递推的“基石”。可以理解为总和为0时只有一种方式——什么都不选。这个初始化保证了后续递推的正确性。递推顺序外层循环i从1到n内层循环j从2到n。这个顺序保证了在计算dp[i][j]时它所依赖的状态dp[i][j-1]和dp[i-j][j]都已经被计算出来了。这是动态规划能正确运行的关键。条件判断if (j i)这是对状态转移方程的修正。当允许的最大加数j大于当前总和i时划分中不可能出现j因此问题退化为dp[i][i]。实操心得在写递推/动态规划代码时我习惯先手动画一个小的DP表比如n5然后手动模拟填充过程。这能帮你直观地理解状态转移和循环顺序是调试和验证逻辑的最有效方法。很多思路上的卡壳画个表就通了。3.3 空间优化滚动数组技巧上面的代码空间复杂度是O(n²)。当n很大时比如n1000这可能成为瓶颈。观察状态转移方程dp[i][j] dp[i][j-1] dp[i-j][j]我们发现计算第i行时只依赖于本行的前一列j-1和上一行的某一列i-j。因此我们可以优化为一维数组。int countPartitionsDP_Optimized(int n) { if (n 0) return 0; vectorlong long dp(n 1, 0); dp[0] 1; // 基础情况 // 核心递推此时外层循环是“最大加数”m内层循环是“总和”i for (int m 1; m n; m) { for (int i m; i n; i) { // dp[i] 表示将i划分成不超过当前m的整数之和的方法数 // 更新前dp[i]保存的是“不超过m-1”的划分数 // 更新后dp[i]需要加上“包含至少一个m”的划分数即dp[i-m] dp[i] dp[i - m]; } } return dp[n]; }优化版解析这个版本的理解角度稍有不同。外层循环的m可以看作是“当前考虑使用的最大硬币面值”内层循环的i是“要凑成的总金额”。dp[i]表示用面值不超过m的硬币凑成金额i的方法数。当m从1遍历到n时我们逐渐将更大的“加数”纳入考虑范围。对于每个idp[i] dp[i-m]的含义是在已有方案使用不超过m-1的加数的基础上加上那些以至少一个m开头的方案。而这些方案的数量正好等于凑成i-m剩下的部分且允许使用m的方案数即当前的dp[i-m]。这个版本代码更简洁效率更高是竞赛中的常用写法。但它背后的思维转换需要时间理解。我建议先彻底掌握二维DP的版本再来看这个一维优化你会对“状态压缩”有更深的认识。4. 递归算法实现与深度分析递归解法更符合人类最直接的思考方式要计算P(n, m)将n划分成不超过m的整数之和我就直接考虑两种情况划分里没有m以及划分里至少有一个m。4.1 递归函数设计与终止条件我们设计递归函数int partition(int n, int m)。函数语义返回将整数n划分成不超过m的正整数之和的方法数。递归关系递推关系情况1划分中不包含m。那么方法数等于partition(n, m-1)。情况2划分中至少包含一个m。那么我们可以先放一个m剩下的n-m继续划分且仍然可以包含m。方法数等于partition(n-m, m)。所以partition(n, m) partition(n, m-1) partition(n-m, m)。看这和我们的递推方程一模一样终止条件递归基如果n 0说明我们已经成功分配完找到一种划分返回1。如果m 0或n 0说明当前路径无效返回0。如果m n那么最大加数m实际上用不上问题等价于partition(n, n)。4.2 C递归代码实现#include iostream using namespace std; // 递归函数计算将n划分成不超过m的正整数之和的方法数 long long partitionRecur(int n, int m) { // 终止条件 if (n 0) return 1; // 找到一种有效的划分 if (m 0 || n 0) return 0; // 无效的路径 if (m n) return partitionRecur(n, n); // 最大加数超过总和等价于partition(n, n) // 递归关系两种情况 // 1. 划分中不包含m方法数 partitionRecur(n, m-1) // 2. 划分中包含至少一个m方法数 partitionRecur(n-m, m) return partitionRecur(n, m-1) partitionRecur(n-m, m); } int main() { int n; cout 请输入一个正整数 n: ; cin n; long long result partitionRecur(n, n); cout 整数 n 的划分数为递归: result endl; return 0; }这段代码非常简洁几乎就是数学定义的直接翻译。输入n4它会展开一棵递归调用树来计算结果。4.3 递归的陷阱重复计算与性能危机虽然递归代码简洁易懂但它有一个致命的缺点大量的重复计算。我们以计算partition(5, 3)为例画出部分递归树partition(5,3) partition(5,2) partition(2,3) [partition(5,1) partition(3,2)] [partition(2,2) partition(-1,3)] ...你会发现像partition(3,2)、partition(2,2)这样的子问题会被不同的父问题多次计算。当n增大到30或40时这棵递归树会变得异常庞大导致程序运行时间呈指数级增长最终超时。踩坑实录我初学递归时曾用这种方法计算n30的划分数程序跑了十几秒都没出结果。这就是典型的“指数爆炸”问题。在算法竞赛中CSP-J的题目时间限制通常是1秒纯递归解法对于n30的数据基本都会超时。4.4 递归的救星记忆化搜索如何保留递归的直观性又避免重复计算答案是记忆化搜索Memoization。其核心思想是“用空间换时间”我们用一个缓存通常是一个二维数组来记录已经计算过的子问题的结果。在递归函数开始时先检查缓存中是否有答案如果有直接返回如果没有才进行计算并将结果存入缓存后再返回。#include iostream #include vector using namespace std; // 记忆化搜索版本 long long partitionMemo(int n, int m, vectorvectorlong long memo) { // 先查表 if (memo[n][m] ! -1) { return memo[n][m]; } // 终止条件 if (n 0) return memo[n][m] 1; if (m 0 || n 0) return 0; // 注意n0的情况在调用前判断更好 if (m n) { memo[n][m] partitionMemo(n, n, memo); return memo[n][m]; } // 递归计算并保存结果 long long res partitionMemo(n, m-1, memo) partitionMemo(n-m, m, memo); memo[n][m] res; return res; } long long countPartitionsMemo(int n) { if (n 0) return 0; // 初始化备忘录-1表示未计算 vectorvectorlong long memo(n 1, vectorlong long(n 1, -1)); return partitionMemo(n, n, memo); } int main() { int n; cout 请输入一个正整数 n: ; cin n; long long result countPartitionsMemo(n); cout 整数 n 的划分数为记忆化搜索: result endl; return 0; }记忆化搜索的精髓memo数组的大小是(n1) x (n1)初始化为-1或任何不会出现的值表示该状态未被计算。在递归函数partitionMemo的开头首先检查memo[n][m]。如果不是-1直接返回避免了重复的递归调用。在返回结果前将计算结果存入memo[n][m]。经过记忆化优化后每个状态(n, m)最多只被计算一次时间复杂度从指数级降到了O(n²)和递推的动态规划完全一样而它的代码结构依然保持着递归的清晰逻辑。核心技巧记忆化搜索是连接递归思维和高效算法的一座桥梁。当你面对一个复杂问题能写出递归解法但担心超时时第一个应该想到的优化手段就是记忆化。它让你既能享受递归“分治”思路的清晰又能获得接近动态规划的效率。5. 递推与递归的对比与选型指南通过上面的详细实现我们可以对两种方法做一个全面的比较特性维度递推动态规划递归记忆化前递归记忆化后思维方式自底向上从基础情况构建自顶向下分解问题自顶向下分解问题代码结构循环嵌套结构清晰函数自我调用简洁直观函数自我调用缓存检查时间复杂度O(n²)O(指数级)极慢O(n²)与递推相同空间复杂度O(n²) 或优化为 O(n)O(n)调用栈深度O(n²)缓存表 O(n)调用栈优点效率高无函数调用开销思路直接易于理解和实现兼具递归的清晰和DP的效率缺点状态转移方程不易想存在大量重复计算n稍大即超时递归调用仍有栈溢出风险n极大时适用场景竞赛主流处理大规模数据仅用于理解思路或极小规模数据当递推顺序难以确定时用记忆化搜索更自然给CSP-J选手的实战建议优先掌握递推/动态规划这是竞赛中的绝对主力。对于“地盘划分”这类经典计数问题要训练自己快速定义状态dp[i][j]代表什么和推导转移方程的能力。递归作为思考工具在纸上分析问题时先用递归的思路去拆分问题想清楚递归关系和终止条件。这能帮你理清逻辑。一旦思路清晰尝试将其转化为递推形式。记忆化搜索是“保底”利器如果比赛时时间紧张或者递推的顺序非常别扭比如某些依赖关系不是简单的从左到右、从上到下那么果断写一个记忆化搜索的递归。它几乎总能保证你得到正确的分数虽然可能不是最优解但远比写不出来的递推或超时的纯递归要好。注意数据范围和溢出像划分数这种问题结果增长很快。务必使用long long甚至高精度来计算和存储结果。在CSP-J中仔细阅读题目中的数据规模约定和结果取模要求如果有的话。6. 举一反三常见变式问题解析掌握了基本模型我们来看看“地盘划分”问题在竞赛中可能出现的几种变式以及如何调整我们的算法。6.1 变式一划分成恰好k个正整数之和定义状态dp[n][k]为将n划分成恰好k个正整数之和的方法数。思考如何转移 我们可以考虑最后一个数第k个数是多少。假设它是x(x 1)那么前k-1个数的和就是n-x并且这k-1个数每个都至少是1。这就将问题转化为了一个子问题。但更巧妙的思路是dp[n][k] dp[n-k][k] dp[n-1][k-1]dp[n-k][k]对应所有划分中每个数都至少为2的情况。我们可以给每个数先减去1总和就变成了n-k但仍然有k个数。dp[n-1][k-1]对应划分中包含至少一个1的情况。我们把这个1拿出来剩下的n-1划分成k-1个数。 这个方程需要仔细理解是动态规划中一种常见的“通过变换保证状态一致性”的技巧。6.2 变式二划分成互不相同的正整数之和这就是整数拆分的另一种形式。定义状态dp[n][m]为将n划分成不超过m的互不相同的正整数之和的方法数。 状态转移需要考虑“不重复”这个限制dp[n][m] dp[n][m-1] dp[n-m][m-1]dp[n][m-1]划分中不包含m。dp[n-m][m-1]划分中包含m。因为要求互不相同既然已经用了一个m剩下的数就不能再超过m-1。6.3 变式三输出具体的划分方案有时题目不仅要求数量还要求输出所有具体的划分方案。这就不能用动态规划了必须使用深度优先搜索DFS其本质就是递归枚举所有可能性。#include iostream #include vector using namespace std; vectorint current; // 存储当前划分方案 // DFS函数寻找将remain划分成不超过max_num的整数之和的所有方案 void dfs(int remain, int max_num) { if (remain 0) { // 找到一种方案输出 for (int i 0; i current.size(); i) { cout current[i]; if (i ! current.size() - 1) cout ; } cout endl; return; } // 从大到小尝试避免重复如31和13被视为相同 // 也可以从小到大但需要额外机制去重 for (int num min(remain, max_num); num 1; --num) { current.push_back(num); // 选择num dfs(remain - num, num); // 剩余部分最大加数不能超过num保证非递增从而去重 current.pop_back(); // 回溯撤销选择 } } int main() { int n; cout 请输入n将输出所有划分方案: ; cin n; current.clear(); dfs(n, n); // 初始时最大加数可以是n return 0; }这个DFS代码通过限制下一次选择的最大数不超过当前选择的数dfs(remain - num, num)保证了输出的划分是非递增的从而自动避免了顺序不同导致的重复方案如31和13。这是输出具体方案时一个非常重要的去重技巧。7. 从“地盘划分”到CSP-J算法学习路径“地盘划分”问题就像一颗种子从中可以生长出算法学习的整棵大树。对于CSP-J的选手我建议按照以下路径以点带面地进行学习基础语法巩固阶段通过实现递推和递归彻底掌握C的循环、数组、函数和递归调用。这是所有算法的基础。递推与简单动态规划将“地盘划分”的递推思想扩展到其他问题如斐波那契数列、爬楼梯、杨辉三角、最大子段和等。理解“状态”和“转移”的概念。深度优先搜索DFS从输出划分方案的DFS代码出发学习回溯法。尝试解决全排列、组合、子集、迷宫路径等问题。这是暴力搜索和优化搜索的基础。记忆化搜索深刻理解记忆化如何将指数级复杂度的递归优化为多项式复杂度。尝试解决经典的“滑雪”、“数字三角形”等问题。正式动态规划当你对记忆化搜索得心应手后动态规划的状态设计和方程推导就会变得自然。这时可以挑战背包问题01背包、完全背包、区间DP、树形DP等更复杂的模型。学习过程中切忌只刷题不总结。每做完一道题尤其是像“地盘划分”这样的经典问题要问自己几个问题这道题的核心模型是什么状态如何定义转移方程为什么这样写有没有更优的解法和之前做过的哪类题相似建立这样的知识关联你的算法能力才能扎实地增长。最后关于工具很多同学问VSCode配置C环境的问题。我的建议是在初学阶段一个简单可靠的IDE如Dev-C、Code::Blocks比VSCode更省心。等到你开始做规模稍大的项目或需要更强大的调试功能时再花时间研究VSCodeMinGW的配置。竞赛备考稳定和熟悉比“高大上”更重要。把时间花在算法思维训练上远比折腾环境带来的收益大得多。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
