1. 划分数问题从计数到动态规划的思维跃迁在算法竞赛和编程面试中动态规划DP常常是区分选手水平的一道分水岭。而“划分数”问题作为计数类DP的经典代表其地位尤为特殊。它不像背包问题那样直观也不像最长公共子序列那样有明确的递推关系。我第一次接触这个问题时感觉就像面对一堆散乱的积木知道要拼出某个形状却不知从何下手。划分数问题问的是将一个正整数n划分成若干个正整数之和有多少种不同的划分方法注意这里“划分”通常指无序划分即12和21被视为同一种划分。这听起来像是一个纯粹的数学组合问题但它却能完美地用动态规划来建模和求解。理解它不仅能让你掌握一种解决特定计数问题的高效工具更重要的是它能极大地锻炼你“将实际问题抽象为状态转移”的DP核心思维能力。很多复杂的资源分配、组合优化问题其内核都与划分数问题相通。今天我们就来彻底拆解这个“有关计数的dp划分数”从最朴素的思路开始一步步推导出高效的DP解法并分享我在实战中积累的调试技巧和思维误区。2. 问题定义与核心难点剖析2.1 什么是“划分数”让我们先严格定义问题。给定一个正整数n我们考虑所有将n表示为一系列正整数之和的方式。例如对于n 443 12 22 1 11 1 1 1总共有5种不同的划分方法。这里有几个关键点需要明确它们直接决定了我们DP状态的定义顺序无关性这是“划分”与“排列”的核心区别。31和13是同一种划分。这要求我们的DP状态设计必须能天然地避免产生顺序不同的重复计数。至少一个部分划分至少包含一个正整数。0不被认为是有效的部分。问题变体有时题目会增加限制条件例如划分成恰好m个部分求将n划分成恰好m个正整数的方案数。每个部分的大小限制例如每个部分不能超过k或者必须是奇数等。互不相同要求划分出的所有正整数互不相同。我们首先聚焦于最基础的、无额外限制的划分数问题。它的难点在于我们无法像处理“序列”问题那样简单地定义dp[i]为前i个元素的某种属性。因为“划分”是集合而非序列。2.2 两种经典DP思路物品视角与容量视角解决计数类DP尤其是划分数关键在于找到一种“构造”划分的方式使得我们在构造过程中能自然地、不重不漏地计数。这里有两条主流的思维路径我称之为“物品视角”和“容量视角”。物品视角整数拆解我们把1, 2, 3, ..., n这些数看作可供选择的“物品”。一次划分相当于从这些物品中可重复地选取若干个使得它们的“重量”之和恰好为n。这听起来很像完全背包问题背包容量为n物品无限多第i种物品的重量和价值都是i求恰好装满背包的方案数。在这个模型里dp[i][j]表示考虑前i种物品即数字1到i凑出总和j的方案数。其状态转移方程为dp[i][j] dp[i-1][j] dp[i][j-i]。 这个方程的含义是对于数字i我们可以选择“不用它”继承dp[i-1][j]或者“至少用一个它”从dp[i][j-i]转移过来因为j-i加上一个i就等于j。通过强制按照数字从小到大的顺序考虑物品我们巧妙地避免了12和21这种因顺序不同导致的重复计数。因为在我们构造方案时数字的出现顺序是单调非减的。容量视角 Ferrers 图与分拆这是另一种非常优美且在某些变体问题上更直观的思路。我们定义dp[i][j]为将整数i划分成不超过j个部分的方案数。或者等价地划分成的最大部分不超过j的方案数。这两种定义通过 Ferrers 图一种用点阵表示整数分拆的图可以互相转化。其状态转移方程为dp[i][j] dp[i-j][j] dp[i][j-1]。 这个方程如何理解考虑将i划分成最大部分不超过j的所有方案。我们可以把这些方案分成两类至少包含一个大小为j的部分那么我们从i中先拿走这个j剩下的i-j仍然需要划分并且划分的最大部分仍然可以不超过j因为允许重复。这部分方案数就是dp[i-j][j]。不包含大小为j的部分那意味着所有部分都小于等于j-1。这部分方案数就是dp[i][j-1]。我个人在入门时更推荐从“物品视角”完全背包入手因为它与经典的背包DP模型衔接更紧密思维负担相对较小。而“容量视角”在处理“划分成m个部分”这类问题时状态定义会更加直接。注意无论哪种视角初始化都是关键。通常dp[0][0] 1表示总和为0、使用0个物品或划分成0个部分有一种方案——“什么都不做”。这是许多计数DP的起点。3. 基础划分数DP的详细实现与优化3.1 基于“完全背包”模型的实现我们以“物品视角”为例给出将n进行无限制划分的完整代码和逐行解析。这里我们采用空间优化后的一维DP数组写法这也是竞赛中的标准写法。def partition_number(n): 计算整数n的划分数无序。 使用完全背包模型的一维DP优化。 # dp[j] 表示凑出总和 j 的方案数 dp [0] * (n 1) dp[0] 1 # 总和为0只有一种方案不选任何数 # 遍历“物品”即数字 1 到 n for i in range(1, n 1): # 遍历“背包容量”即总和 j # 注意这里必须正序遍历因为每种数字物品可以无限次使用完全背包。 for j in range(i, n 1): dp[j] dp[j - i] # 如果需要取模防止溢出可以在这里进行例如 # dp[j] (dp[j] dp[j - i]) % MOD return dp[n] # 测试 if __name__ __main__: for n in range(1, 11): print(fp({n}) {partition_number(n)})代码逻辑拆解与思考dp[0] 1这是所有计数DP的“种子”。它表示凑出总和0的方案数为1即空划分。没有这个初始状态整个递推就无法启动。外层循环for i in range(1, n1)i代表当前考虑的数字。我们从小到大考虑数字这是保证划分“无序性”的关键。想象一下如果我们先考虑大数字再考虑小数字在构造方案211时可能会先放2再放两个1而另一种构造顺序可能先放两个1再放2。由于DP是累计过程这可能导致重复计数。而强制从小到大考虑相当于我们生成的划分方案其数字序列总是非递减的如[1,1,2]自然就唯一了。内层循环for j in range(i, n1)j代表当前要凑出的总和。为什么从i开始因为如果j i那么当前数字i比目标总和还大根本不可能被使用所以直接从j i开始遍历。状态转移dp[j] dp[j-i]这是完全背包的经典转移。dp[j-i]是凑出总和j-i的方案数。对于其中每一种方案我们只需要再添加一个数字i就能得到一种凑出总和j的新方案。由于i是从小到大遍历的并且j是正序更新这意味着在计算dp[j]时dp[j-i]可能已经包含了本轮循环中即考虑当前数字i时新产生的方案。这正好对应了数字i可以被重复使用多次的特性。时间复杂度与空间复杂度时间复杂度为 O(n²)空间复杂度为 O(n)。对于n在几千以内的题目这个效率是完全可接受的。3.2 从基础到变体划分成恰好m个部分现在我们来解决一个常见的变体将n划分成恰好m个正整数部分的方案数。这时“容量视角”的状态定义就显示出优势了。我们定义dp[i][j]为将整数i划分成恰好j个部分的方案数。如何转移考虑这j个部分中最小的那个数注意我们依然要维持无序性所以考虑“最小数”是一个常见的切入口如果最小的数是 1那么我们可以把这个 1 拿走剩下的问题就变成了将i-1划分成恰好j-1个部分。方案数为dp[i-1][j-1]。如果最小的数大于 1那么我们可以给这j个部分每个都减去 1。这样总和就变成了i - j部分个数仍然是j并且每个部分仍然至少是 1因为原来最小数1减1后1。这就等价于将i-j划分成恰好j个部分。方案数为dp[i-j][j]。因此状态转移方程为dp[i][j] dp[i-1][j-1] dp[i-j][j]其中i j否则无法划分成 j 个正数部分。边界条件dp[0][0] 1。def partition_into_m_parts(n, m): 计算将整数n划分成恰好m个正整数的方案数。 if m n: return 0 dp [[0] * (m 1) for _ in range(n 1)] dp[0][0] 1 for i in range(1, n 1): # j 不能超过 i也不能超过 m for j in range(1, min(i, m) 1): dp[i][j] dp[i-1][j-1] if i j: dp[i][j] dp[i-j][j] # 同样可以在这里取模 return dp[n][m]这个例子清晰地展示了面对变体问题时灵活地定义状态这里是“部分数” j和寻找不重不漏的转移分类这里是基于“最小数”的性质是多么重要。4. 实战中的边界、初始化与调试技巧动态规划尤其是计数DP代码可能很短但思维和调试的“坑”却不少。下面是我在大量练习后总结的几个核心要点。4.1 边界条件与初始化陷阱dp[0]的含义在计数DP中dp[0]或dp[0][0]几乎总是等于 1。它代表“达成空状态”有一种方案。在划分数问题中dp[0]1表示“总和为0有一种划分方案即不进行任何划分空集”。这是一个非常重要的逻辑起点没有它后续所有状态都无法被正确计算。下标越界在状态转移时如dp[j] dp[j-i]必须确保j-i 0。我们的循环for j in range(i, n1)天然保证了这一点。但在其他变体或更复杂的转移中务必在访问数组前检查下标。无效状态例如在“划分成m个部分”的问题中当i j时dp[i][j]应该是 0因为不可能用比部分数还小的数划分出那么多部分。我们的循环条件for j in range(1, min(i, m) 1)就处理了这个问题。4.2 调试方法论打印DP表与手算小数据当你觉得程序输出不对时最有效的调试方法就是打印出整个DP表并与你手算的小规模结果进行对比。例如对于n5的基础划分数我们可以手算 p(5) 7 (划分方案5, 41, 32, 311, 221, 2111, 11111)然后在partition_number函数中在内层循环结束后打印dp数组def partition_number_debug(n): dp [0] * (n 1) dp[0] 1 for i in range(1, n 1): print(f\n考虑数字 i {i}:) old_dp dp[:] # 保存旧状态用于对比 for j in range(i, n 1): dp[j] dp[j - i] # 打印本次更新后的dp数组 for j in range(n1): if dp[j] ! old_dp[j]: print(f dp[{j}] 从 {old_dp[j]} 变为 {dp[j]}) print(f 当前dp数组: {dp}) return dp[n]运行partition_number_debug(5)你会看到dp数组如何一步步从[1,0,0,0,0,0]演变成最终的[1,1,2,3,5,7]。观察这个演变过程能帮你深刻理解“完全背包”正序更新的含义以及每个数字i是如何贡献的。4.3 大数取模与常见问题划分数增长非常快p(100) 已经是一个巨大的数字。因此题目通常要求对结果取模如10^97。取模操作必须在每次加法后进行而不是最后才取模否则中间结果可能溢出。MOD 10**9 7 dp[j] (dp[j] dp[j - i]) % MOD # 正确做法 # dp[j] dp[j - i] # 错误可能溢出另一个常见错误是混淆“至少一个”和“可以为零”。在有些问题中划分的部分允许为0这通常不是标准划分数那么初始化条件和转移方程会完全不同。务必仔细阅读题面。5. 从划分数延展与其他DP模型的联系与思维训练掌握基础划分数后你会发现它的思想能迁移到许多其他DP问题上。联系1硬币找零问题。求用若干种面额的硬币每种无限多凑出金额n的方案数。这几乎就是划分数问题的“物品视角”模型只是“物品”的重量变成了硬币面额不一定是连续的1到n。状态定义和转移方程一模一样。联系2整数拆分求最大乘积。这是LeetCode上一道经典题343. 整数拆分。给定正整数n将其拆分为至少两个正整数的和并使这些整数的乘积最大化。虽然求的是最大乘积而非方案数但其“拆分”的本质与划分数同源。通常的DP解法定义dp[i]为数字i拆分后能得到的最大乘积其转移需要枚举拆出的第一个数字jdp[i] max(j * (i-j), j * dp[i-j])。你可以看到这里依然是在枚举“第一部分”的大小与划分数中“考虑最大数或最小数”的思路一脉相承。联系3有依赖的划分/分配问题。例如将n个任务分配给m个不同的服务器每个服务器至少一个任务且任务之间有依赖关系如某个任务必须和另一个任务在同一服务器。这类问题通常需要结合状压DP或树形DP。但划分的框架分成m组仍然是基础只是组内元素的组合不再是任意的而是受限于图或树的拓扑结构。这时状态可能需要记录当前已分配的集合状压转移时考虑将某个连通块整体放入一个新组。思维训练建议从小规模暴力搜索开始对于n 10的划分数尝试写一个DFS函数枚举所有划分方案并计数。观察生成的方案体会“从小到大”枚举如何避免重复。这个直观感受对理解DP的状态设计至关重要。尝试不同的状态定义除了上述两种还可以定义dp[i][j]为将i划分且最大部分恰好为 j的方案数。推导它的转移方程。多角度思考能极大加深理解。解决变体问题主动寻找和尝试以下变体并思考状态定义如何调整划分成奇数个部分/偶数个部分。所有部分都是奇数/偶数。所有部分互不相同这就是经典的“子集和”问题01背包模型。划分数问题就像一把钥匙打开的是计数类动态规划的大门。它的价值不在于背下一个模板而在于通过它学会如何将模糊的“计数”需求转化为精确的、可递推的“状态”和“转移”。下次当你遇到一个复杂的计数问题时不妨问问自己这个问题能不能看作一种特殊的“划分”如果能我的“部分”是什么“总和”是什么限制条件如何体现在状态维度里想清楚这些你就离AC不远了。