尧图网页设计 
1. 项目概述从一道经典竞赛题看“划分数”的实战价值在算法竞赛和日常的编程面试中我们经常会遇到一类关于“分配”或“分割”的问题。比如有N个无差别的苹果要分给M个盘子允许有的盘子空着问有多少种不同的分法或者将一个整数N拆分成若干个正整数之和不考虑顺序有多少种拆分方式这类问题背后都指向一个核心的数学模型——划分数Partition Number。我第一次在《挑战程序设计竞赛》这类经典书籍里系统学习它时就被其简洁定义下蕴含的深刻数学思想和巧妙的动态规划解法所吸引。它不仅是组合数学中的一个优美课题更是解决许多实际编程难题的利器。简单来说划分数 P(n, k) 表示将正整数 n 拆分成恰好 k 个正整数之和的方案数。而更常见的 P(n) 则表示将 n 拆分成任意多个正整数之和的方案数即所有 k 从 1 到 n 的 P(n, k) 之和。理解并掌握计算划分数的方法能让你在面对“资源分配”、“任务分解”、“组合计数”等场景时快速找到建模方向和高效算法避免陷入暴力枚举的泥潭。无论你是正在备战算法竞赛的学生还是希望提升问题抽象能力的开发者划分数都是一个值得深入研究的工具。接下来我将结合《挑战程序设计竞赛》中的思路拆解其核心算法、多种变体以及实战中的避坑技巧。2. 核心概念与问题定义拆解在深入代码之前我们必须把“划分数”这个模型本身吃透。很多初学者容易混淆几个相似的概念导致建模错误全盘皆输。2.1 精确区分划分数 vs. 分配问题这是最容易混淆的点。我们通过两个经典问题来辨析问题A划分数将整数 4 拆分成正整数之和不考虑顺序。那么 112 和 121 被视为同一种拆分。所有拆分为4, 31, 22, 211, 1111。所以 P(4) 5。问题B分配问题/整数拆分将4个相同的苹果分给3个相同的盘子允许空盘。这听起来和划分数很像但关键在于“盘子相同”。这意味着分配方案 (1, 1, 2) 和 (2, 1, 1) 被视为同一种因为盘子没有编号。这实质上就是求将整数4拆分成最多3个部分的划分数即 P(4,1) P(4,2) P(4,3)。如果盘子是不同的那就是经典的“隔板法”问题方案数为 C(nm-1, m-1)与划分数完全不同。所以判断是否使用划分数模型第一个关键就是看“组成部分是否有序”。如果无序才可能用到划分数。2.2 关键参数n 与 k 的约束与含义在动态规划求解 P(n, k) 时对 n 和 k 的理解直接决定了状态定义。n (总和)必须是一个正整数。在动态规划中它通常作为状态的第一维。k (部分数)表示拆分出的正整数的个数。k 的取值范围是 1 ≤ k ≤ n。当 k n 时P(n, k) 0因为不可能用超过 n 个正整数每个至少为1去凑出总和 n。递推关系的基石所有划分数动态规划递推式的核心都源于对拆分中最小项或最大项的讨论。这是理解所有解法的钥匙。2.3 问题常见变体与建模掌握了基础定义我们就能处理各种变体限定部分数求 P(n, k)。这是最标准的子问题。限定部分大小每个拆分数不能超过 m或必须大于等于 m。这可以通过修改递推式的初始条件或转移范围来实现。奇拆分/偶拆分所有拆分数都是奇数或都是偶数。这有非常优美的生成函数结论但也可以用动态规划结合奇偶性状态来解。互异拆分所有拆分数必须两两不同。例如5的互异拆分有5, 41, 32。在竞赛中题目往往会披上各种应用的外衣比如“将价值n的资产拆分成k个等价值的项目”、“一种化学分子式由k个相同基团构成的总质量为n的同分异构体数量”等等。核心能力就是剥离表象识别出“无序整数拆分”的内核。注意务必仔细阅读题目描述中的“是否考虑顺序”、“组成部分是否相同”等字眼。一个词的差异意味着完全不同的数学模型和算法复杂度。3. 核心算法解析从基础DP到五边形数定理计算划分数的主流方法有两种动态规划DP和基于五边形数定理的生成函数法。DP易于理解适合解决带各种约束的变体五边形数定理效率极高专攻大规模 n 的 P(n) 计算。3.1 基础动态规划解法这是《挑战程序设计竞赛》中重点介绍的方法也是我们必须掌握的核心。状态定义 设dp[i][j]表示将整数i拆分成恰好j个正整数之和的方案数。递推关系推导基于最小项 考虑拆分中的最小数。如果最小数等于1那么拿走这个1剩下的部分就是将i-1拆分成j-1个数的方案数即dp[i-1][j-1]。如果最小数大于 1那么我们可以将拆分中的每个数都减去1。这样总和就变成了i-j因为j个数各减1而数的个数仍然是j。这就对应了将i-j拆分成j个数的方案数即dp[i-j][j]。因此我们得到核心递推式dp[i][j] dp[i-1][j-1] dp[i-j][j]其中这个递推式仅在i j时有效。当i j时dp[i][j] 0。初始化dp[0][0] 1。这可以理解为“总和为0用0个数来表示”有一种方案空表示。这个初始化是保证递推起点的关键。对于任意i 0,dp[i][0] 0。因为不可能用0个正整数表示一个正数。代码实现计算 P(n, k)def partition_number_dp(n, k): # 初始化一个 (n1) x (k1) 的二维数组所有元素为0 dp [[0] * (k 1) for _ in range(n 1)] dp[0][0] 1 # 初始化 for i in range(1, n 1): # j 不能超过 i因为部分数不可能超过总和本身 for j in range(1, min(i, k) 1): dp[i][j] dp[i-1][j-1] dp[i-j][j] return dp[n][k] # 示例计算将5拆分成2个数的方案数 print(partition_number_dp(5, 2)) # 输出2 (对应 41, 32)复杂度分析时间复杂度 O(n * k)空间复杂度 O(n * k)。可以通过滚动数组优化空间到 O(n)但竞赛中通常 n 和 k 不会太大几百到几千二维数组足以应对。3.2 另一种DP思路基于最大项的“完全背包”模型这是一种更直观且易于推广到其他变形的思路。我们可以把问题看作有无限个重量为 1, 2, 3, ... 的物品要恰好装满容量为 n 的背包并且恰好选择 k 个物品求方案数。这里“重量”就是拆分数的大小。状态定义dp[j][t]表示使用前i种数字隐含维度通过遍历实现总重量为j且物品总数量为t的方案数。递推关系完全背包计数 这是一个三维DP的优化过程。最朴素的是三重循环dp [[0]*(k1) for _ in range(n1)] dp[0][0] 1 for num in range(1, n1): # 枚举“物品”数字 for j in range(num, n1): # 枚举总重量 for t in range(1, k1): # 枚举物品个数 dp[j][t] dp[j-num][t-1]我们可以优化掉num这一维通过正序枚举j来实现“无限个”完全背包的效果。但注意这里还需要计数个数t所以内层对t的循环需要倒序类似于0-1背包以确保每个数字在本次大循环中只被使用一次不这里有个精妙之处为了计算“恰好k个”我们需要一个三维的思路或者更巧妙的定义。实际上更清晰的写法是定义一个二维状态dp_sum[count][weight]然后外层循环数字num。但竞赛中更常见的优化是使用“最大数不超过m的拆分”这个角度。定义dp[i][j]为将i拆分成若干个不超过j的正整数之和的方案数。其递推为dp[i][j] dp[i][j-1] dp[i-j][j](当 ij)。这个递推可以用来求 P(n)但控制部分数 k 稍麻烦。实操心得对于新手我强烈推荐掌握第一种基于最小项的DP解法。它思路直接状态定义与问题完美对应代码简洁且易于修改以适应“部分数不超过k”、“部分数至少为k”等变体。第二种背包模型虽然强大但在处理“恰好k个”这个约束时状态设计需要更多技巧容易出错。3.3 高效算法五边形数定理当题目只要求计算 P(n)不限定k且 n 非常大例如 n ≤ 10^5时O(n^2) 的DP就无法胜任了。这时就需要数学武器——五边形数定理。定理给出了整数拆分生成函数的一个惊人等式并导出一个 O(n√n) 时间复杂度的递推式P(n) Σ_{k≠0} (-1)^{k-1} * P(n - g_k)其中g_k k*(3k-1)/2是广义五边形数求和遍历所有使得n - g_k 0的整数 k正负均可。代码实现def partition_number_pentagonal(n): partitions [0] * (n 1) partitions[0] 1 # P(0) 1 MOD 10**9 7 # 通常结果会要求取模因为P(n)增长极快 for i in range(1, n 1): k 1 while True: pent1 k * (3*k - 1) // 2 # 正五边形数 if pent1 i: break # 根据k的奇偶性决定符号 sign -1 if k % 2 0 else 1 partitions[i] (partitions[i] sign * partitions[i - pent1]) % MOD pent2 k * (3*k 1) // 2 # 另一个广义五边形数 if pent2 i: k 1 continue partitions[i] (partitions[i] sign * partitions[i - pent2]) % MOD k 1 return partitions[n]这个算法效率很高可以瞬间计算出 n10^5 的 P(n)取模后。但它只能计算 P(n)无法计算 P(n, k)。注意事项使用五边形数定理时一定要注意取模运算。因为划分数 P(n) 随着 n 增大会爆炸性增长远超任何基本数据类型的范围。竞赛题目中几乎一定会要求对一个大质数如1e97取模。4. 实战应用与变体题目解析理解了核心算法我们来看几个变体以及如何调整我们的DP状态。4.1 变体一限定部分大小的划分数问题计算将 n 拆分成恰好 k 个正整数且每个数都不超过 m 的方案数。解法在基础DP上增加一个维度或者修改递推范围。定义dp[i][j]为将 i 拆分成 j 个不超过当前考虑上限的数的方案数。更实用的方法是使用“最大数恰好为某值”的思路。 我们可以定义f[i][j][max]状态但这样复杂度高。一个巧妙的转化是计算“不超过m”的方案数等于P(n, k)减去“至少有一个数大于m”的方案数。后者可以通过容斥原理或另一个DP来求。在竞赛中如果 m 的限制比较特殊往往需要重新推导递推式。示例思路定义dp[i][j]同前。在递推dp[i][j] dp[i-1][j-1] dp[i-j][j]时这个递推天然保证了所有数 1。但要保证所有数 m就需要在从dp[i-j][j]转移时确保i-j的拆分方案里的数都 m。这很难直接控制。因此更稳健的方法是采用“最大数不超过m”的DPdp[i][j] dp[i][j-1] dp[i-j][j]其中 j 现在是“使用的最大数”。最终答案是dp[n][m] - dp[n][m-1]最大数恰好为m。但这求的是总划分数不是恰好k个。为了控制个数可能需要三维状态dp[i][j][c]表示总和i最大数为j用了c个数。复杂度 O(nmk)在参数较小时可行。4.2 变体二互异划分数问题计算将 n 拆分成 k 个互不相同的正整数的方案数。解法此时经典的递推不再适用。我们可以回到“背包”模型但每个数字只能选0次或1次0-1背包。定义dp[i][j]为使用前 i 个不同的数1,2,...,i总和为 j恰好选了 k 个数的方案数。其状态转移为dp[i][j][k] dp[i-1][j][k] dp[i-1][j-i][k-1]即不考虑数字 i或者考虑数字 i那么总和减少 i所用数字个数增加1。这可以通过滚动数组优化空间。代码框架def distinct_partition(n, k): # dp[j][t] 表示总和为j用了t个不同数字的方案数 dp [[0]*(k1) for _ in range(n1)] dp[0][0] 1 for num in range(1, n1): # 枚举当前考虑的数字 # 必须倒序枚举以保证每个数字最多用一次0-1背包 for j in range(n, num-1, -1): for t in range(1, k1): dp[j][t] dp[j-num][t-1] return dp[n][k]4.3 变体三奇划分数问题计算将 n 拆分成全部为奇数的正整数的方案数。解法这是一个著名的定理将 n 拆分成奇数个不同正整数之和的方案数等于将 n 拆分成互不相同的正整数之和的方案数。但如果我们只是求所有部分为奇数的划分数不要求互异也有一个优美的结论它等于将 n 拆分成互不相同的正整数之和的方案数即互异划分数 P_distinct(n)。这个可以用生成函数证明。在编程中我们可以用类似互异划分的DP但数字只从奇数中选取1,3,5,...或者利用上述结论直接计算互异划分数。5. 竞赛中的典型陷阱与调试技巧即使理解了算法在紧张的竞赛中实现划分数DP也常会出错。下面是我踩过坑后总结的排查清单。5.1 初始化错误这是最常见的错误。dp[0][0] 1这个初始化非常反直觉但至关重要。可以这样理解总和为0用0个数字来表示存在一种“空方案”。它是所有递推的起点。如果将其设为0那么所有dp[i][i]即拆分成i个1的情况都无法被正确计算因为dp[i][i]依赖于dp[0][0]。检查方法手动计算小样例比如 n1, k1 和 n2, k2。P(1,1)1,P(2,2)1只有11。用你的程序跑一下看结果是否正确。5.2 数组越界在递推式dp[i][j] dp[i-1][j-1] dp[i-j][j]中访问dp[i-j][j]时必须确保i-j 0。虽然在循环中我们限制了j i但i-j有可能为0这是合法的因为dp[0][j]在j0时应该是0。我们需要确保dp数组的第一维大小是n1并且对i-j的访问不会越界i-j最小为0。在代码中我们通过for j in range(1, min(i, k)1)来保证i j从而i-j 0。5.3 模运算下的减法当结果需要取模时递推式中的减法可能导致负数。例如dp[i][j] (dp[i-1][j-1] dp[i-j][j]) % MOD没问题。但在五边形数定理中项partitions[i] - partitions[i - pent]如果得到负数需要加上 MOD 调整到非负。partitions[i] (partitions[i] sign * partitions[i - pent1] MOD) % MOD更安全的写法是partitions[i] (partitions[i] sign * partitions[i - pent1]) % MODif partitions[i] 0: partitions[i] MOD5.4 时间复杂度与空间复杂度估计错误基础DPO(n*k)。如果 n 和 k 达到 5000运算量是 2.5e7在2秒时限内 C 可以过但 Python 可能比较极限。需要评估语言性能。五边形数定理O(n√n)。对于 n1e5循环次数约为 n * (2√n/3) ≈ 2e7也是可行的。空间基础DP需要 O(nk) 的数组。如果 n5000, k5000一个 int 数组就占用 50005000*4 bytes ≈ 100MB可能超过内存限制。此时必须使用滚动数组优化到 O(n) 或 O(k)。滚动数组优化示例计算 P(n, k)def partition_number_dp_rolling(n, k): # 只保留两行 dp_prev [0] * (k 1) dp_curr [0] * (k 1) dp_prev[0] 1 # 对应 i0 行 for i in range(1, n 1): dp_curr [0] * (k 1) for j in range(1, min(i, k) 1): dp_curr[j] dp_prev[j-1] (dp_curr[j] if i-j 0 else dp_curr[j]) # 注意这里需要dp_curr[i-j][j]但i-j i所以实际上需要的是“当前行”的之前状态 # 等等这里有问题dp[i-j][j] 中的 i-j 小于 i所以它可能已经在本次i的循环中被更新了或者还在上一行 # 正确的滚动需要仔细设计因为递推依赖了两个不同“行”的状态。实际上这个递推dp[i][j] dp[i-1][j-1] dp[i-j][j]同时依赖于上一行 (i-1) 和同一行但更小的索引 (i-j)。标准的二维滚动难以直接应用。一个办法是改变状态定义或者使用“最大数不超过m”的DP那种递推dp[i][j] dp[i][j-1] dp[i-j][j]更容易用滚动数组优化按特定顺序枚举。5.5 思维定式混淆问题模型再次强调一定要分清是“划分数”无序还是“分配问题”有序隔板法。一个简单的测试用例n4, k3。如果盘子相同无序方案有 (2,1,1), (1,1,1,1?) 不对k3所以是 (2,1,1) 和 (1,1,2) 是同一种还有 (1,1,1,1)是4个数了。实际上将4拆成最多3个部分P(4,1)P(4,2)P(4,3)1214。具体是4, 31, 22, 211。如果盘子不同有序方案数是 C(43-1, 3-1)C(6,2)15。用你的程序计算 P(4,3)1只有211而分配问题有15种。如果题目要求后者你用了划分数DP就会得到错误答案。6. 性能优化与扩展思考对于大规模问题我们需要更优的算法和实现。6.1 空间优化进阶当 n 和 k 很大时即使 O(n*k) 的时间能接受空间也可能成为瓶颈。除了滚动数组我们可以观察状态依赖。对于递推式dp[i][j] dp[i-1][j-1] dp[i-j][j]dp[i][j]只依赖于dp[i-1][j-1]左上角和dp[i-j][j]同一行左边较远的位置。如果我们按 i 从1到nj从1到i的顺序计算并且只保留一行历史数据会发现dp[i-j][j]可能已经被覆盖如果 i-j i。因此一个可行的优化是使用二维数组但只开辟dp[k1][n1]其中第一维是部分数 j第二维是和 i。递推式变为dp[j][i] dp[j-1][i-1] dp[j][i-j]。这样在更新dp[j][i]时dp[j][i-j]位于同一行j行的左侧已经被计算过因为 i-j i而dp[j-1][i-1]位于上一行。我们可以按行j优先的顺序计算这样只需要两行数组即可。6.2 五边形数定理的边界处理在实现五边形数定理时循环的终止条件pent1 i和pent2 i必须仔细处理。广义五边形数g_k在 k 为负数时也有定义但通常我们按公式k*(3k-1)/2计算并让 k 取正负值。在代码中更高效的方法是让 k 从1开始递增同时计算pent1 k*(3k-1)//2和pent2 k*(3k1)//2它们分别对应正 k 和负 k 的绝对值。当pent1 n且pent2 n时就可以提前结束循环因为后续的 pent 值会更大。6.3 结合具体问题的状态设计很多竞赛题不会直接问 P(n, k)而是将其作为子问题嵌套在更大的DP中。例如问题可能是“有多少种方式将一个字符串分割成k个子序列使得每个子序列的和构成一个特定集合” 这时你可能需要先预处理出所有可能的子序列和对应的划分数然后再进行组合。关键在于识别出哪个环节对应着“无序拆分”模型。通常当问题中涉及到“一组数”、“一堆物品”且这组数内部没有顺序区分时就要考虑划分数。我个人在实战中的体会是划分数DP的代码不长但思维密度高。在比赛时如果识别出这是划分数问题通常意味着找到了正确的突破口剩下的就是仔细实现和调试。建议在练习时将基础DP的代码包括滚动数组优化版和五边形数定理的代码封装成模板函数并准备好常用的变体如互异拆分。这样在赛场上可以快速调用将精力集中在问题建模上而不是重新推导递推公式。最后多用手算的小样例n5来验证你的程序这是最快最有效的调试手段。 划分数（Partition Number）算法精讲：从动态规划到五边形数定理
1. 项目概述从一道经典竞赛题看“划分数”的实战价值在算法竞赛和日常的编程面试中我们经常会遇到一类关于“分配”或“分割”的问题。比如有N个无差别的苹果要分给M个盘子允许有的盘子空着问有多少种不同的分法或者将一个整数N拆分成若干个正整数之和不考虑顺序有多少种拆分方式这类问题背后都指向一个核心的数学模型——划分数Partition Number。我第一次在《挑战程序设计竞赛》这类经典书籍里系统学习它时就被其简洁定义下蕴含的深刻数学思想和巧妙的动态规划解法所吸引。它不仅是组合数学中的一个优美课题更是解决许多实际编程难题的利器。简单来说划分数 P(n, k) 表示将正整数 n 拆分成恰好 k 个正整数之和的方案数。而更常见的 P(n) 则表示将 n 拆分成任意多个正整数之和的方案数即所有 k 从 1 到 n 的 P(n, k) 之和。理解并掌握计算划分数的方法能让你在面对“资源分配”、“任务分解”、“组合计数”等场景时快速找到建模方向和高效算法避免陷入暴力枚举的泥潭。无论你是正在备战算法竞赛的学生还是希望提升问题抽象能力的开发者划分数都是一个值得深入研究的工具。接下来我将结合《挑战程序设计竞赛》中的思路拆解其核心算法、多种变体以及实战中的避坑技巧。2. 核心概念与问题定义拆解在深入代码之前我们必须把“划分数”这个模型本身吃透。很多初学者容易混淆几个相似的概念导致建模错误全盘皆输。2.1 精确区分划分数 vs. 分配问题这是最容易混淆的点。我们通过两个经典问题来辨析问题A划分数将整数 4 拆分成正整数之和不考虑顺序。那么 112 和 121 被视为同一种拆分。所有拆分为4, 31, 22, 211, 1111。所以 P(4) 5。问题B分配问题/整数拆分将4个相同的苹果分给3个相同的盘子允许空盘。这听起来和划分数很像但关键在于“盘子相同”。这意味着分配方案 (1, 1, 2) 和 (2, 1, 1) 被视为同一种因为盘子没有编号。这实质上就是求将整数4拆分成最多3个部分的划分数即 P(4,1) P(4,2) P(4,3)。如果盘子是不同的那就是经典的“隔板法”问题方案数为 C(nm-1, m-1)与划分数完全不同。所以判断是否使用划分数模型第一个关键就是看“组成部分是否有序”。如果无序才可能用到划分数。2.2 关键参数n 与 k 的约束与含义在动态规划求解 P(n, k) 时对 n 和 k 的理解直接决定了状态定义。n (总和)必须是一个正整数。在动态规划中它通常作为状态的第一维。k (部分数)表示拆分出的正整数的个数。k 的取值范围是 1 ≤ k ≤ n。当 k n 时P(n, k) 0因为不可能用超过 n 个正整数每个至少为1去凑出总和 n。递推关系的基石所有划分数动态规划递推式的核心都源于对拆分中最小项或最大项的讨论。这是理解所有解法的钥匙。2.3 问题常见变体与建模掌握了基础定义我们就能处理各种变体限定部分数求 P(n, k)。这是最标准的子问题。限定部分大小每个拆分数不能超过 m或必须大于等于 m。这可以通过修改递推式的初始条件或转移范围来实现。奇拆分/偶拆分所有拆分数都是奇数或都是偶数。这有非常优美的生成函数结论但也可以用动态规划结合奇偶性状态来解。互异拆分所有拆分数必须两两不同。例如5的互异拆分有5, 41, 32。在竞赛中题目往往会披上各种应用的外衣比如“将价值n的资产拆分成k个等价值的项目”、“一种化学分子式由k个相同基团构成的总质量为n的同分异构体数量”等等。核心能力就是剥离表象识别出“无序整数拆分”的内核。注意务必仔细阅读题目描述中的“是否考虑顺序”、“组成部分是否相同”等字眼。一个词的差异意味着完全不同的数学模型和算法复杂度。3. 核心算法解析从基础DP到五边形数定理计算划分数的主流方法有两种动态规划DP和基于五边形数定理的生成函数法。DP易于理解适合解决带各种约束的变体五边形数定理效率极高专攻大规模 n 的 P(n) 计算。3.1 基础动态规划解法这是《挑战程序设计竞赛》中重点介绍的方法也是我们必须掌握的核心。状态定义 设dp[i][j]表示将整数i拆分成恰好j个正整数之和的方案数。递推关系推导基于最小项 考虑拆分中的最小数。如果最小数等于1那么拿走这个1剩下的部分就是将i-1拆分成j-1个数的方案数即dp[i-1][j-1]。如果最小数大于 1那么我们可以将拆分中的每个数都减去1。这样总和就变成了i-j因为j个数各减1而数的个数仍然是j。这就对应了将i-j拆分成j个数的方案数即dp[i-j][j]。因此我们得到核心递推式dp[i][j] dp[i-1][j-1] dp[i-j][j]其中这个递推式仅在i j时有效。当i j时dp[i][j] 0。初始化dp[0][0] 1。这可以理解为“总和为0用0个数来表示”有一种方案空表示。这个初始化是保证递推起点的关键。对于任意i 0,dp[i][0] 0。因为不可能用0个正整数表示一个正数。代码实现计算 P(n, k)def partition_number_dp(n, k): # 初始化一个 (n1) x (k1) 的二维数组所有元素为0 dp [[0] * (k 1) for _ in range(n 1)] dp[0][0] 1 # 初始化 for i in range(1, n 1): # j 不能超过 i因为部分数不可能超过总和本身 for j in range(1, min(i, k) 1): dp[i][j] dp[i-1][j-1] dp[i-j][j] return dp[n][k] # 示例计算将5拆分成2个数的方案数 print(partition_number_dp(5, 2)) # 输出2 (对应 41, 32)复杂度分析时间复杂度 O(n * k)空间复杂度 O(n * k)。可以通过滚动数组优化空间到 O(n)但竞赛中通常 n 和 k 不会太大几百到几千二维数组足以应对。3.2 另一种DP思路基于最大项的“完全背包”模型这是一种更直观且易于推广到其他变形的思路。我们可以把问题看作有无限个重量为 1, 2, 3, ... 的物品要恰好装满容量为 n 的背包并且恰好选择 k 个物品求方案数。这里“重量”就是拆分数的大小。状态定义dp[j][t]表示使用前i种数字隐含维度通过遍历实现总重量为j且物品总数量为t的方案数。递推关系完全背包计数 这是一个三维DP的优化过程。最朴素的是三重循环dp [[0]*(k1) for _ in range(n1)] dp[0][0] 1 for num in range(1, n1): # 枚举“物品”数字 for j in range(num, n1): # 枚举总重量 for t in range(1, k1): # 枚举物品个数 dp[j][t] dp[j-num][t-1]我们可以优化掉num这一维通过正序枚举j来实现“无限个”完全背包的效果。但注意这里还需要计数个数t所以内层对t的循环需要倒序类似于0-1背包以确保每个数字在本次大循环中只被使用一次不这里有个精妙之处为了计算“恰好k个”我们需要一个三维的思路或者更巧妙的定义。实际上更清晰的写法是定义一个二维状态dp_sum[count][weight]然后外层循环数字num。但竞赛中更常见的优化是使用“最大数不超过m的拆分”这个角度。定义dp[i][j]为将i拆分成若干个不超过j的正整数之和的方案数。其递推为dp[i][j] dp[i][j-1] dp[i-j][j](当 ij)。这个递推可以用来求 P(n)但控制部分数 k 稍麻烦。实操心得对于新手我强烈推荐掌握第一种基于最小项的DP解法。它思路直接状态定义与问题完美对应代码简洁且易于修改以适应“部分数不超过k”、“部分数至少为k”等变体。第二种背包模型虽然强大但在处理“恰好k个”这个约束时状态设计需要更多技巧容易出错。3.3 高效算法五边形数定理当题目只要求计算 P(n)不限定k且 n 非常大例如 n ≤ 10^5时O(n^2) 的DP就无法胜任了。这时就需要数学武器——五边形数定理。定理给出了整数拆分生成函数的一个惊人等式并导出一个 O(n√n) 时间复杂度的递推式P(n) Σ_{k≠0} (-1)^{k-1} * P(n - g_k)其中g_k k*(3k-1)/2是广义五边形数求和遍历所有使得n - g_k 0的整数 k正负均可。代码实现def partition_number_pentagonal(n): partitions [0] * (n 1) partitions[0] 1 # P(0) 1 MOD 10**9 7 # 通常结果会要求取模因为P(n)增长极快 for i in range(1, n 1): k 1 while True: pent1 k * (3*k - 1) // 2 # 正五边形数 if pent1 i: break # 根据k的奇偶性决定符号 sign -1 if k % 2 0 else 1 partitions[i] (partitions[i] sign * partitions[i - pent1]) % MOD pent2 k * (3*k 1) // 2 # 另一个广义五边形数 if pent2 i: k 1 continue partitions[i] (partitions[i] sign * partitions[i - pent2]) % MOD k 1 return partitions[n]这个算法效率很高可以瞬间计算出 n10^5 的 P(n)取模后。但它只能计算 P(n)无法计算 P(n, k)。注意事项使用五边形数定理时一定要注意取模运算。因为划分数 P(n) 随着 n 增大会爆炸性增长远超任何基本数据类型的范围。竞赛题目中几乎一定会要求对一个大质数如1e97取模。4. 实战应用与变体题目解析理解了核心算法我们来看几个变体以及如何调整我们的DP状态。4.1 变体一限定部分大小的划分数问题计算将 n 拆分成恰好 k 个正整数且每个数都不超过 m 的方案数。解法在基础DP上增加一个维度或者修改递推范围。定义dp[i][j]为将 i 拆分成 j 个不超过当前考虑上限的数的方案数。更实用的方法是使用“最大数恰好为某值”的思路。 我们可以定义f[i][j][max]状态但这样复杂度高。一个巧妙的转化是计算“不超过m”的方案数等于P(n, k)减去“至少有一个数大于m”的方案数。后者可以通过容斥原理或另一个DP来求。在竞赛中如果 m 的限制比较特殊往往需要重新推导递推式。示例思路定义dp[i][j]同前。在递推dp[i][j] dp[i-1][j-1] dp[i-j][j]时这个递推天然保证了所有数 1。但要保证所有数 m就需要在从dp[i-j][j]转移时确保i-j的拆分方案里的数都 m。这很难直接控制。因此更稳健的方法是采用“最大数不超过m”的DPdp[i][j] dp[i][j-1] dp[i-j][j]其中 j 现在是“使用的最大数”。最终答案是dp[n][m] - dp[n][m-1]最大数恰好为m。但这求的是总划分数不是恰好k个。为了控制个数可能需要三维状态dp[i][j][c]表示总和i最大数为j用了c个数。复杂度 O(nmk)在参数较小时可行。4.2 变体二互异划分数问题计算将 n 拆分成 k 个互不相同的正整数的方案数。解法此时经典的递推不再适用。我们可以回到“背包”模型但每个数字只能选0次或1次0-1背包。定义dp[i][j]为使用前 i 个不同的数1,2,...,i总和为 j恰好选了 k 个数的方案数。其状态转移为dp[i][j][k] dp[i-1][j][k] dp[i-1][j-i][k-1]即不考虑数字 i或者考虑数字 i那么总和减少 i所用数字个数增加1。这可以通过滚动数组优化空间。代码框架def distinct_partition(n, k): # dp[j][t] 表示总和为j用了t个不同数字的方案数 dp [[0]*(k1) for _ in range(n1)] dp[0][0] 1 for num in range(1, n1): # 枚举当前考虑的数字 # 必须倒序枚举以保证每个数字最多用一次0-1背包 for j in range(n, num-1, -1): for t in range(1, k1): dp[j][t] dp[j-num][t-1] return dp[n][k]4.3 变体三奇划分数问题计算将 n 拆分成全部为奇数的正整数的方案数。解法这是一个著名的定理将 n 拆分成奇数个不同正整数之和的方案数等于将 n 拆分成互不相同的正整数之和的方案数。但如果我们只是求所有部分为奇数的划分数不要求互异也有一个优美的结论它等于将 n 拆分成互不相同的正整数之和的方案数即互异划分数 P_distinct(n)。这个可以用生成函数证明。在编程中我们可以用类似互异划分的DP但数字只从奇数中选取1,3,5,...或者利用上述结论直接计算互异划分数。5. 竞赛中的典型陷阱与调试技巧即使理解了算法在紧张的竞赛中实现划分数DP也常会出错。下面是我踩过坑后总结的排查清单。5.1 初始化错误这是最常见的错误。dp[0][0] 1这个初始化非常反直觉但至关重要。可以这样理解总和为0用0个数字来表示存在一种“空方案”。它是所有递推的起点。如果将其设为0那么所有dp[i][i]即拆分成i个1的情况都无法被正确计算因为dp[i][i]依赖于dp[0][0]。检查方法手动计算小样例比如 n1, k1 和 n2, k2。P(1,1)1,P(2,2)1只有11。用你的程序跑一下看结果是否正确。5.2 数组越界在递推式dp[i][j] dp[i-1][j-1] dp[i-j][j]中访问dp[i-j][j]时必须确保i-j 0。虽然在循环中我们限制了j i但i-j有可能为0这是合法的因为dp[0][j]在j0时应该是0。我们需要确保dp数组的第一维大小是n1并且对i-j的访问不会越界i-j最小为0。在代码中我们通过for j in range(1, min(i, k)1)来保证i j从而i-j 0。5.3 模运算下的减法当结果需要取模时递推式中的减法可能导致负数。例如dp[i][j] (dp[i-1][j-1] dp[i-j][j]) % MOD没问题。但在五边形数定理中项partitions[i] - partitions[i - pent]如果得到负数需要加上 MOD 调整到非负。partitions[i] (partitions[i] sign * partitions[i - pent1] MOD) % MOD更安全的写法是partitions[i] (partitions[i] sign * partitions[i - pent1]) % MODif partitions[i] 0: partitions[i] MOD5.4 时间复杂度与空间复杂度估计错误基础DPO(n*k)。如果 n 和 k 达到 5000运算量是 2.5e7在2秒时限内 C 可以过但 Python 可能比较极限。需要评估语言性能。五边形数定理O(n√n)。对于 n1e5循环次数约为 n * (2√n/3) ≈ 2e7也是可行的。空间基础DP需要 O(nk) 的数组。如果 n5000, k5000一个 int 数组就占用 50005000*4 bytes ≈ 100MB可能超过内存限制。此时必须使用滚动数组优化到 O(n) 或 O(k)。滚动数组优化示例计算 P(n, k)def partition_number_dp_rolling(n, k): # 只保留两行 dp_prev [0] * (k 1) dp_curr [0] * (k 1) dp_prev[0] 1 # 对应 i0 行 for i in range(1, n 1): dp_curr [0] * (k 1) for j in range(1, min(i, k) 1): dp_curr[j] dp_prev[j-1] (dp_curr[j] if i-j 0 else dp_curr[j]) # 注意这里需要dp_curr[i-j][j]但i-j i所以实际上需要的是“当前行”的之前状态 # 等等这里有问题dp[i-j][j] 中的 i-j 小于 i所以它可能已经在本次i的循环中被更新了或者还在上一行 # 正确的滚动需要仔细设计因为递推依赖了两个不同“行”的状态。实际上这个递推dp[i][j] dp[i-1][j-1] dp[i-j][j]同时依赖于上一行 (i-1) 和同一行但更小的索引 (i-j)。标准的二维滚动难以直接应用。一个办法是改变状态定义或者使用“最大数不超过m”的DP那种递推dp[i][j] dp[i][j-1] dp[i-j][j]更容易用滚动数组优化按特定顺序枚举。5.5 思维定式混淆问题模型再次强调一定要分清是“划分数”无序还是“分配问题”有序隔板法。一个简单的测试用例n4, k3。如果盘子相同无序方案有 (2,1,1), (1,1,1,1?) 不对k3所以是 (2,1,1) 和 (1,1,2) 是同一种还有 (1,1,1,1)是4个数了。实际上将4拆成最多3个部分P(4,1)P(4,2)P(4,3)1214。具体是4, 31, 22, 211。如果盘子不同有序方案数是 C(43-1, 3-1)C(6,2)15。用你的程序计算 P(4,3)1只有211而分配问题有15种。如果题目要求后者你用了划分数DP就会得到错误答案。6. 性能优化与扩展思考对于大规模问题我们需要更优的算法和实现。6.1 空间优化进阶当 n 和 k 很大时即使 O(n*k) 的时间能接受空间也可能成为瓶颈。除了滚动数组我们可以观察状态依赖。对于递推式dp[i][j] dp[i-1][j-1] dp[i-j][j]dp[i][j]只依赖于dp[i-1][j-1]左上角和dp[i-j][j]同一行左边较远的位置。如果我们按 i 从1到nj从1到i的顺序计算并且只保留一行历史数据会发现dp[i-j][j]可能已经被覆盖如果 i-j i。因此一个可行的优化是使用二维数组但只开辟dp[k1][n1]其中第一维是部分数 j第二维是和 i。递推式变为dp[j][i] dp[j-1][i-1] dp[j][i-j]。这样在更新dp[j][i]时dp[j][i-j]位于同一行j行的左侧已经被计算过因为 i-j i而dp[j-1][i-1]位于上一行。我们可以按行j优先的顺序计算这样只需要两行数组即可。6.2 五边形数定理的边界处理在实现五边形数定理时循环的终止条件pent1 i和pent2 i必须仔细处理。广义五边形数g_k在 k 为负数时也有定义但通常我们按公式k*(3k-1)/2计算并让 k 取正负值。在代码中更高效的方法是让 k 从1开始递增同时计算pent1 k*(3k-1)//2和pent2 k*(3k1)//2它们分别对应正 k 和负 k 的绝对值。当pent1 n且pent2 n时就可以提前结束循环因为后续的 pent 值会更大。6.3 结合具体问题的状态设计很多竞赛题不会直接问 P(n, k)而是将其作为子问题嵌套在更大的DP中。例如问题可能是“有多少种方式将一个字符串分割成k个子序列使得每个子序列的和构成一个特定集合” 这时你可能需要先预处理出所有可能的子序列和对应的划分数然后再进行组合。关键在于识别出哪个环节对应着“无序拆分”模型。通常当问题中涉及到“一组数”、“一堆物品”且这组数内部没有顺序区分时就要考虑划分数。我个人在实战中的体会是划分数DP的代码不长但思维密度高。在比赛时如果识别出这是划分数问题通常意味着找到了正确的突破口剩下的就是仔细实现和调试。建议在练习时将基础DP的代码包括滚动数组优化版和五边形数定理的代码封装成模板函数并准备好常用的变体如互异拆分。这样在赛场上可以快速调用将精力集中在问题建模上而不是重新推导递推公式。最后多用手算的小样例n5来验证你的程序这是最快最有效的调试手段。