动态规划解整数划分数问题：从状态定义到空间优化

1. 项目概述从一道经典竞赛题说起“划分数”这个题目但凡刷过《挑战程序设计竞赛》也就是大家常说的“白书”或“蟋蟀书”的朋友应该都不陌生。它静静地躺在动态规划的章节里看似不起眼却像一块试金石能清晰地区分出一个人对DP的理解是停留在“背模板”的层面还是真正掌握了其“状态定义”与“转移方程”设计的精髓。我第一次遇到它时也卡壳了很久总觉得和经典的背包问题有点像但又处处透着不同。后来在无数次调试和与队友的争论中才慢慢摸清了它的门道。今天我就想以一个过来人的身份把这个问题的里里外外、前因后果以及那些书本上不会写的“坑”和“技巧”掰开揉碎了讲清楚。简单来说“划分数”问题描述的是给定一个正整数n和m考虑将整数n划分成不超过m个正整数之和的方案数。这里“划分”意味着顺序无关即12和21被视为同一种划分。举个例子n4, m3那么所有划分是4,31,22,211。注意1111是4个部分超过了m3所以不计入。我们的目标就是计算出这个方案数。这个问题在组合数学、算法竞赛乃至一些资源分配、任务拆分的实际建模中都有其身影。理解它不仅是解决一道题更是打开“整数划分”这类问题的一把钥匙。2. 核心思路拆解为什么动态规划是正解面对这个问题新手最容易想到的是暴力搜索DFS枚举每个部分的大小。但稍加分析就会发现n稍微大一点比如50搜索空间就会爆炸因为划分的方案数是指数级增长的。这时动态规划DP几乎是必然的选择。DP的核心思想是用空间换时间将重叠子问题的解存储起来避免重复计算。2.1 状态定义的两种视角与抉择定义DP状态是解题的第一步也是最关键的一步。对于划分数常见的有两种定义方式它们源于对问题不同的理解角度最终也会导致不同的转移方程和初始化。第一种定义“背包”视角dp[i][j]表示使用前i种数字通常考虑数字1到i凑出总和为j的方案数。这种想法很自然因为它把每个数字1, 2, 3, …看作一种物品可以无限次使用因为一个划分里可以有多个1多个2等目标总和是n。这就是一个经典的“完全背包”问题模型。但是这里有一个陷阱完全背包求的是“组合数”它本身已经保证了顺序无关因为先选1还是先选2不影响最终方案。然而我们还需要额外处理“不超过m个部分”这个限制。这需要在状态中增加一维来表示已使用的数字个数或者最后对满足个数限制的方案进行求和使得状态变得复杂dp[k][i][j]表示用前i种数恰好使用k个数凑出总和j的方案数。三维状态在时间和空间上开销都更大。第二种定义“分拆”视角dp[i][j]表示将整数i划分成不超过j个部分的方案数。这是更贴近问题原意的定义。i对应总和nj对应部分数上限m。这个定义直接包含了“部分数”的限制状态就是两维更加简洁。它的思考方式不是“用什么数字去凑”而是“直接审视这个划分本身的结构”。《挑战程序设计竞赛》书中采用的就是这种定义。我个人的体会是一旦理解了这种状态的含义其转移方程会非常优美和高效是竞赛中的首选思路。因此后续我们将深入剖析这种定义下的解法。2.2 转移方程的推导寻找子问题关联现在我们采用第二种定义dp[i][j] 将i划分成不超过j个正整数的方案数。如何从较小的子问题推导出dp[i][j]呢这里需要一个关键的分类讨论切入点就是划分中是否包含数字1。划分中不包含1这意味着划分中的所有部分都至少是2。那么我们可以从每个部分中都减去1。例如一个将i划分成不超过j个部分、且每部分2的方案比如i8的一个划分3323个部分。如果从每个部分减1就变成了221总和变成了8 - 3 5部分数仍然是3。反过来任何一个将5划分成恰好3个部分的方案给每个部分加1就能得到一个将8划分成恰好3个部分且每部分2的方案。注意这里“不超过j个”在减1操作后变成了“恰好j个”因为只有原划分恰好用了j个部分时减1后才仍有j个部分。如果原划分用了少于j个部分减1后部分数不变但我们的状态是“不超过”所以需要一点转换。更严谨的推导是考虑“将i划分成恰好j个部分”的方案数记为dp_exact[i][j]。那么“不包含1”的情况就等价于dp_exact[i - j][j]先给j个部分每个预分配一个1剩下的i-j再划分给j个部分。划分中包含1那么至少有一个部分是1。我们可以直接把这个1拿走。拿走一个1后总和变成i-1部分数上限可以认为是j-1因为我们至少用掉了一个部分来放这个1。所以这部分方案数对应dp[i-1][j-1]。因此如果我们定义dp[i][j]为将i划分成不超过j个部分的方案数其转移方程可以通过上述“恰好j个部分”的中间量来推导但最终可以整合为一个简洁的形式。书中给出的经典转移方程是dp[i][j] dp[i][j-1] dp[i-j][j]其中需要满足i j。这个方程如何理解呢dp[i][j-1]这部分对应了“部分数不超过j-1个”的所有方案。显然这些方案自然也满足“部分数不超过j个”。这是情况一的一种聚合表示。dp[i-j][j]这部分对应了“所有部分都至少为2”的方案。正如之前分析的我们可以从i中先取出j个1每个部分先分配一个1保证至少有j个部分如果实际划分部分数少于j可以认为有一些部分初始分配了1但最终大小为0不这里更准确的理解是dp[i][j]包含了“部分数恰好为1, 2, …, j”的所有情况。dp[i-j][j]这个项实际上是通过一个技巧涵盖了所有部分都2的划分无论其部分数是多少但不超过j。想象一下对于任何一个所有部分2的划分我们给每个部分减1得到的新划分总和为i-j部分数不变且不超过j。这个新划分就是dp[i-j][j]所计数的对象之一。反之亦然。所以dp[i-j][j]完美地映射了“所有部分2”的划分。注意这个转移方程成立的前提是i j。当i j时dp[i][j] dp[i][i]。因为用超过i个正整数来划分i是不可能的最小的划分是i个1所以部分数上限超过i没有意义等同于上限为i。2.3 初始化与边界条件任何DP都离不开正确的初始化。dp[0][j] 1将0划分成不超过j个部分有一种方案就是“什么都不划分”0个部分。这是一个空划分通常计为1种方案。dp[i][0] 0(当i 0时)将正数i划分成不超过0个部分是不可能的方案数为0。有了状态定义、转移方程和边界条件这个DP模型就完整了。它的时间复杂度是 O(n * m)空间复杂度通过滚动数组可以优化到 O(n)对于竞赛常见的n, m 1000甚至更大都是完全可以接受的。3. 代码实现与逐行解析理论清晰后我们来看代码实现。这里我会给出两个版本一个是直观的二维DP版本便于理解另一个是优化了空间的一维DP滚动数组版本这是竞赛中更常用的写法。3.1 基础二维DP实现#include iostream #include vector using namespace std; int main() { int n, m; int MOD 1000000007; // 通常结果很大需要取模 cin n m; // dp[i][j]: 将i划分成不超过j个部分的方案数 vectorvectorint dp(n 1, vectorint(m 1, 0)); // 初始化 for (int j 0; j m; j) { dp[0][j] 1; // 总和为0只有一种划分空划分 } // dp[i][0] (i0) 已经由vector初始化为了0符合定义 // DP计算 for (int i 1; i n; i) { for (int j 1; j m; j) { if (i j) { // 核心转移方程 dp[i][j] (dp[i][j-1] dp[i-j][j]) % MOD; } else { // 当 i j 时dp[i][j] dp[i][i] dp[i][j] dp[i][i]; } } } cout dp[n][m] endl; return 0; }逐行解析dp数组大小是(n1) x (m1)包含了从0到n的总和以及从0到m的部分数上限。初始化dp[0][j]1。注意这里i0的循环单独处理了i0时dp[i][0]默认为0。双重循环i从1到nj从1到m。注意顺序必须先遍历i或者j吗在这个转移方程中dp[i][j]依赖于dp[i][j-1]同一行左侧和dp[i-j][j]上一行左侧的某个位置。因此无论是先i后j还是先j后i只要保证在计算dp[i][j]时它所依赖的状态都已经计算出来即可。当前先i后j的遍历顺序是安全的。核心if (i j)分支执行转移方程。这里直接对应了公式。else分支处理i j的情况直接等于dp[i][i]。这里dp[i][i]一定已经在之前计算出来了因为i n,i m在循环范围内。3.2 空间优化一维滚动数组二维数组在n和m很大时会消耗大量内存。观察转移方程dp[i][j] dp[i][j-1] dp[i-j][j]我们发现计算第i行第j列时需要用到同一行 (i) 的前一列 (j-1)。第i-j行 (i-j) 的第j列。这意味着如果我们按j部分数上限作为外层循环内层循环i总和并且使用一维数组dp[i]来存储当前j下所有i对应的方案数那么dp[i][j-1]就是当前一维数组在计算dp[i]时已经更新过的值因为j-1是上一轮或本轮更小的i这里需要仔细。实际上更常见的优化是按j递增的顺序进行完全背包式的更新。但针对这个特定的方程有一个更巧妙的滚动方式。我们定义一维数组dp[i]但在双重循环中固定j部分数上限然后递增地更新i总和。让我们重新审视方程dp[i][j] dp[i][j-1] dp[i-j][j]当我们固定j时dp[i][j-1]是上一轮j-1计算完成后得到的结果也就是当前dp数组在未开始本轮j计算时的值。我们可以用另一个数组prev_dp来保存。dp[i-j][j]是本轮j在计算到i时已经计算出的dp[i-j]的值因为i-j i且我们是从小到大遍历i的。因此算法可以这样实现#include iostream #include vector using namespace std; int main() { int n, m; int MOD 1000000007; cin n m; vectorint dp(n 1, 0); dp[0] 1; // 初始化总和为0的方案数为1 for (int j 1; j m; j) { // 枚举部分数上限j for (int i j; i n; i) { // 注意i从j开始因为ij时dp[i][j]dp[i][i]而dp[i][i]会在后续的j增大到i时被计算。 // 此时dp[i]中存储的实际上是 dp[i][j-1] (因为j循环在外部i循环内部更新dp[i]) // 我们需要用到一个临时变量来保存旧的dp[i]吗不我们可以直接更新。 // dp[i] dp[i] dp[i-j]; // 这里的 dp[i] 在等号右边是“旧的”代表 dp[i][j-1] // dp[i-j] 在等号右边是“新的”代表 dp[i-j][j]因为i是从小到大遍历所以dp[i-j]在本轮j中已经更新过了。 dp[i] (dp[i] dp[i-j]) % MOD; } } cout dp[n] endl; return 0; }这个一维版本的代码极其简洁。它的核心在于外层循环j代表当前考虑的部分数上限。内层循环i从j到n因为当i j时根据定义dp[i][j] dp[i][i]而这个值会在j增大到i时在本轮ji的内层循环中被计算出来i从j开始循环当ji时i从i到n会计算dp[i]其中就包括了dp[i][i]。状态转移dp[i] dp[i] dp[i-j]直接在一维数组上原地更新。这里的dp[i]在加法右边代表的是“上一轮j-1”的结果即dp[i][j-1]而dp[i-j]代表的是“本轮j”中已经计算出的dp[i-j][j]。因为i是递增的所以dp[i-j]一定在本轮已经更新过了。实操心得这个一维DP的写法是竞赛中的标准答案务必理解其“固定部分数上限j然后做完全背包式更新”的内涵。它和完全背包问题的一维优化dp[v] dp[v] dp[v-w]在形式上很像但含义不同。这里j不是物品的重量而是部分数的上限同时也是状态转移中的一个“偏移量”。多写几遍手动模拟n4, m3的过程就能深刻体会。4. 深入理解与其他整数划分问题的联系“划分数”只是整数划分家族中的一个成员。理解它能帮助我们触类旁通。这里对比几个常见的变种问题描述状态定义示例关键转移思想与本题 (dp[n][m]) 的关系本题将n划分成不超过m个正整数之和dp[i][j]: 将i划分成不超过j个部分dp[i][j] dp[i][j-1] dp[i-j][j](ij)原问题变种1将n划分成恰好m个正整数之和dp_exact[i][j]: 将i划分成恰好j个部分dp_exact[i][j] dp_exact[i-1][j-1] dp_exact[i-j][j]dp_exact[n][m] dp[n][m] - dp[n][m-1]变种2将n划分成最大数不超过k的正整数之和dp_max[i][j]: 将i划分且最大部分不超过jdp_max[i][j] dp_max[i][j-1] dp_max[i-j][j]形式上与本题方程一模一样但i,j含义不同。这揭示了划分问题中“部分数上限”和“部分大小上限”的对偶性。变种3将n划分成互不相同的正整数之和通常使用生成函数或另一种DP思路状态需记录已使用的最大数避免重复与本题思路差异较大更接近背包中的“01背包”。重点看变种2。它的方程dp_max[i][j] dp_max[i][j-1] dp_max[i-j][j]和我们的方程在数学形式上完全一致。这背后是组合数学中一个深刻的对偶原理将一个整数n划分成不超过m个部分的方案数等于将n划分成每个部分都不超过m的方案数。这个原理可以通过绘制“Ferrers图”来直观证明将划分的每一行看作一个部分转置后行数就变成了最大部分值。这个洞察能让你的理解提升一个维度——你解决的不仅仅是一个问题而是一类问题的核心。注意事项在编码时虽然方程一样但循环的边界和初始化的细节可能因定义不同而有微妙差别。比如在变种2中dp_max[0][j]1依然成立但dp_max[i][0] (i0)可能为0因为最大数不超过0无法组成正数。务必根据具体定义重新推导不要死记硬背。5. 典型问题与调试技巧即使理解了算法实现时也可能踩坑。下面是我和队友们“血泪史”总结出的常见问题。5.1 初始化错误问题忽略了dp[0][j] 1。如果你将其设为0那么所有状态都将推导为0。调试从小样例开始。计算n1, m1。手动算答案是1划分1。如果你的程序输出0首先检查初始化。dp[0][0]、dp[0][1]等都应该是1。5.2 转移条件遗漏问题只写了dp[i][j] dp[i][j-1] dp[i-j][j]忘记了i j时的处理。现象当m n时程序可能访问非法下标dp[i-j][j]因为i-j可能为负或者得到错误结果。修正务必加上if (i j) ... else dp[i][j] dp[i][i];的判断。在一维DP中通过内层循环i从j开始巧妙地规避了这个问题。5.3 模运算陷阱问题结果很大需要取模。但在计算过程中两个数相加可能溢出即使它们各自都小于模数。代码示例// 错误写法可能溢出 dp[i][j] dp[i][j-1] dp[i-j][j]; dp[i][j] % MOD; // 正确写法加法前或后取模 dp[i][j] (dp[i][j-1] dp[i-j][j]) % MOD; // 或者 dp[i][j] dp[i][j-1] dp[i-j][j]; if (dp[i][j] MOD) dp[i][j] - MOD; // 如果MOD是质数且加法不超过2*MOD可以用减法的形式更快。5.4 一维DP更新顺序的理解误区问题在写一维DP时混淆了更新顺序错误地写成了类似完全背包的形式。// 危险这是完全背包的循环顺序但对此题不一定正确 for (int i 1; i n; i) { for (int j 1; j m; j) { if (i j) dp[i] dp[i-j]; } }这段代码的问题在于它没有区分“部分数上限j”这个维度。内层循环对同一个idp[i-j]可能被用不同的j重复累加多次导致结果远大于真实值。它实际上计算的是“将i划分成若干正整数之和且每个正整数可以是1到m”的方案数这忽略了“部分数”的限制变成了另一种划分问题变种2的某种版本。切记一维DP的外层循环必须是部分数上限j。5.5 测试用例设计自己测试时不要只用书上的例子。设计几组小的、能手算的测试用例n1, m1- 1n4, m3- 4 划分4, 31, 22, 211n5, m2- 3 划分5, 41, 32n5, m5- 7 所有划分5, 41, 32, 311, 221, 2111, 11111n0, m任意- 1 空划分n任意, m0(n0) - 0用这些用例去验证你的程序能快速定位大部分逻辑错误。6. 性能分析与扩展思考6.1 时间复杂度与空间复杂度二维DP时间复杂度 O(n * m)空间复杂度 O(n * m)。在n, m 5000时通常可以接受空间约 500050004字节 ≈ 100MB处于边界。一维DP时间复杂度 O(n * m)空间复杂度 O(n)。这是竞赛中的首选几乎可以处理n, m 10000甚至更大的数据只要时间允许。6.2 扩展如果要求输出具体划分方案怎么办DP只能计数不能直接输出方案。如果需要输出所有具体划分必须使用回溯法DFS。但我们可以利用DP的计算结果进行“剪枝”或“按字典序生成”这属于另一个话题。一个常见的技巧是在DFS时保持划分的每个部分非递增即后一部分不大于前一部分这样可以避免生成重复的排列如31和13并且自然生成字典序。6.3 扩展非常大的n和m怎么办当n和m大到几千甚至上万时O(n*m) 的DP可能超时。此时需要更高级的算法例如五边形数定理计算整数划分部分数不限的数目有著名的欧拉公式可以通过生成函数和五边形数来 O(n√n) 计算。但对于有部分数上限m的情况需要更复杂的生成函数处理。Meet-in-the-Middle对于非常大的n有时可以将问题拆分成两半分别计算部分和再组合。但这在划分问题中不常用。近似算法或数学公式在非竞赛场景有时只需要近似值或渐进公式。对于绝大多数程序设计竞赛掌握 O(n*m) 的DP解法已经足够应对。7. 总结与个人体会“划分数”问题就像动态规划领域的一个经典范式。它教会我们的不仅仅是这个特定的状态和转移更是一种思考方式如何通过分类讨论这里是以“是否包含1”来分类将一个大问题分解成规模更小的子问题如何选择最贴合问题本质的状态定义“不超过j个部分”比“使用前i种数”更直接以及如何利用对偶性部分数上限与部分大小上限来洞察不同问题之间的联系。我在初学的时候曾试图强行套用完全背包的模板结果搞得非常复杂。后来才明白理解问题本身的结构比套用已知模型更重要。写代码时从二维DP开始写起确保逻辑正确再优化到一维是一个稳妥的路径。那个一维转移的for (int j1; jm; j) for (int ij; in; i) dp[i] dp[i-j];已经成了我的肌肉记忆。最后一个小技巧如果题目问的是“恰好m个部分”而你又只写了“不超过m个部分”的代码别慌答案就是dp[n][m] - dp[n][m-1]当m1时。这个关系在很多计数问题中都成立体现了“不超过”和“恰好”之间的紧密联系。