动态规划计数问题精讲：从划分数到完全背包的算法实现

1. 项目概述从“划分数”切入动态规划的计数世界最近在整理算法笔记翻到了“划分数”这个经典的动态规划问题。它不像背包问题那样直接也不像最长公共子序列那样常见于面试但恰恰是这种“计数类”的DP问题最能考验我们对状态定义和转移方程本质的理解。很多朋友在刷题时一遇到需要“数一数有多少种方案”的题目就发怵感觉思路和之前求最值、判存活的DP不太一样。其实一旦你掌握了计数DP的核心——把“加法原理”和“乘法原理”融入状态转移很多难题都会迎刃而开。今天我们就以“划分数”这个经典模型作为引子彻底拆解计数型动态规划的设计思路、实现细节和那些容易踩进去的坑。所谓“划分数”简单说就是给定一个正整数n问有多少种方法可以将其表示为若干个正整数之和。这里顺序不同视为同一种方法。例如n4的划分有4,31,22,211,1111共5种。这个问题看似是纯粹的数学组合问题但其动态规划的解法却蕴含着处理“无序组合计数”的通用思想是理解完全背包、整数拆分乃至生成函数等更高级概念的绝佳起点。无论你是正在备战算法竞赛还是希望深化对DP的理解吃透这个问题都大有裨益。2. 核心思路拆解如何为“计数”设计状态面对一个计数问题我们首先要问到底要“数”什么对于划分数最直接的答案是“数”将n划分成若干正整数之和的方案总数。但直接定义dp[n]为方案总数会遇到一个棘手的问题如何保证我们数的方案不重不漏因为划分是无序的211和121被视为同一种我们的状态必须能天然地规避“顺序”带来的重复计数。2.1 两种经典的状态定义哲学经过前人的总结主要有两种定义状态的方式它们代表了两种不同的思考角度最终却殊途同归。第一种定义基于“最大加数”的限制定义dp[i][j]为将正整数i划分成若干个正整数且这些正整数不超过j的方案数。 这种定义的精妙之处在于它通过限制划分中出现的最大数字人为地引入了一种“顺序”。我们可以按照最大加数的情况来进行分类讨论从而得到一个清晰且不重复的计数方式。这是最符合直觉、教学中最常采用的定义。第二种定义基于“物品”的完全背包视角我们可以把正整数1, 2, 3, ..., n看作无限供应的“物品”每个物品的价值就是其本身的数值。那么将n进行划分就等价于从这些物品中挑选每个物品可以选无限次使得挑选出的物品总价值恰好为n的方案数。这里我们不考虑顺序因为12和21在背包问题中对应的是同一种物品组合。此时我们可以定义dp[i][j]为考虑前i种物品即数字1到i凑出总价值j的方案数。这本质上是一个完全背包的计数问题。注意这两种定义看似不同但内在联系紧密。第一种定义中的“最大加数不超过 j”在第二种定义中相当于“只允许使用数字 1 到 j 这些物品”。在实际编码中第二种背包视角往往更容易实现和优化。2.2 状态转移方程的推导我们以第一种定义dp[i][j]将i划分为最大加数不超过j的方案数为例来推导状态转移方程。这是理解计数DP分类讨论思想的关键。对于dp[i][j]我们可以根据划分中是否包含j这个数字将所有的方案分成互斥且完备的两类划分中不包含j既然最大加数连j都不包含那么实际上最大加数最多是j-1。所以这类方案数就是dp[i][j-1]。划分中至少包含一个j我们可以先从i中拿走一个j那么剩下的部分是i-j。对于剩下的i-j我们仍然可以继续划分并且划分中的数字最大可以是多少注意因为原划分中已经包含了一个j为了不重复计数避免出现j之后又出现比j大的数导致最大数变化我们通常约定剩下的部分其最大加数也不超过j。这样这类方案数就是dp[i-j][j]。这里有一个关键点为什么第二类转移是dp[i-j][j]而不是dp[i-j][j-1]因为我们要允许剩下的部分仍然可以包含j。例如i6, j3一种划分是33。它属于“至少包含一个3”的类别。拿走一个3后剩下3对剩下的3进行“最大加数不超过3”的划分方案是dp[3][3]其中就包含了3这一种即剩下的部分就是一个3从而组合回33。如果限制为dp[i-j][j-1]那么33这种方案就会被漏掉。因此我们得到状态转移方程dp[i][j] dp[i][j-1] dp[i-j][j]其中i j。 如果i j那么最大加数j本身已经超过了i所以实际上最大加数不可能达到j方案数等同于dp[i][i]。但更简单的处理是在i j时直接让dp[i][j] dp[i][i]。边界条件dp[0][j] 1将0划分成若干正整数可以理解为不划分的方案数通常定义为1种空划分。dp[i][0] 0(当i0时)不允许使用任何正整数自然无法组成任何正数。2.3 从二维到一维空间优化观察方程dp[i][j] dp[i][j-1] dp[i-j][j]。在计算dp[i][j]时它依赖于本行的前一项dp[i][j-1]和上一行的某一项dp[i-j][j]。如果我们按i从1到nj从1到n的顺序进行递推在计算dp[i][j]时dp[i-j][j]可能还没有被计算因为i-j i。因此通常我们固定j最大加数然后让i递增或者采用其他遍历顺序。更常见且易于优化的是第二种定义——完全背包视角。定义dp[j]为凑出总价值j的方案数。初始时dp[0] 1凑出0的方案就是不选1种。然后我们遍历“物品”i(从1到n)对于每个i我们更新容量j(从i到n)dp[j] dp[j - i]。 这个转移的含义是为了凑出金额j我们可以考虑在之前所有方案的基础上再添加一个数字i。由于i是从小到大遍历的并且j也是顺序遍历这天然保证了我们是在做完全背包的计数并且不会重复计算顺序例如先选1再选2和先选2再选1被视为同一种组合。这是计数类完全背包最简洁优美的形式。3. 代码实现与细节剖析理论清晰之后实现就是水到渠成。但代码的细节里藏着决定正确与否的魔鬼。3.1 基于完全背包的一维DP实现这是最推荐、最常用的实现方式代码简洁效率高。def partition_number(n): 计算整数n的划分数无序。 使用完全背包思路的一维DP。 # dp[j] 表示凑成总和j的方案数 dp [0] * (n 1) dp[0] 1 # 总和为0的方案数为1空划分 # 遍历“物品”即正整数1, 2, ..., n for i in range(1, n 1): # 遍历“背包容量”从i到n正序更新完全背包 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)})这段代码的输出应该对应著名的整数划分序列1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ...关键细节解读dp[0] 1这是所有计数DP的基石。它代表了“什么都不做”也是一种方案。在划分中它对应着“0的划分”是空集有1种方式。外层循环是i(物品)内层循环是j(容量)这保证了我们是在逐个考虑每个数字是否可以加入划分。顺序遍历j使得数字i可以被重复使用符合完全背包特性。内层循环j从i开始因为如果j i那么j - i 0没有意义。从i开始可以避免不必要的判断。3.2 基于二维DP的实现教学理解版为了更清晰地对应我们之前的状态定义这里给出二维DP的实现帮助理解状态转移的过程。def partition_number_2d(n): 计算整数n的划分数。 使用dp[i][j]: 将i划分成最大加数不超过j的方案数。 # 初始化 (n1) x (n1) 的二维数组 dp [[0] * (n 1) for _ in range(n 1)] # 边界条件dp[0][j] 1 for j in range(n 1): dp[0][j] 1 # dp[i][0] 0 (i0) 在初始化时已经是0无需额外设置 # 递推 for i in range(1, n 1): for j in range(1, n 1): if i j: # 状态转移方程 dp[i][j] dp[i][j - 1] dp[i - j][j] else: # 当 i j 时最大加数实际为 i dp[i][j] dp[i][i] # 最终答案将n划分最大加数不超过n即无限制 return dp[n][n]这个版本直观展示了状态转移的分类讨论逻辑但空间复杂度为 O(n²)。在算法竞赛或工程中一维版本是首选。3.3 大数处理与模运算整数的划分数p(n)随着n增大会急剧增长。例如p(100)已经是一个巨大的数字。在大多数编程题中通常会要求结果对一个素数如10^97取模。修改上述一维代码以支持取模非常简单MOD 10**9 7 def partition_number_mod(n): dp [0] * (n 1) dp[0] 1 for i in range(1, n 1): for j in range(i, n 1): dp[j] (dp[j] dp[j - i]) % MOD # 每次加法后取模 return dp[n]注意取模运算虽然简单但务必在每次加法后立即进行防止中间结果溢出。这是计数DP中的常见要求。4. 变种问题与扩展思考掌握了基本模型我们来看看“划分数”的几个经典变种。这些变种通常只修改状态定义或转移方程的一小部分但却能解决完全不同的问题。4.1 变种一划分成恰好k个数的方案数问题将正整数n划分成恰好k个正整数之和的方案数是多少思路分析 此时我们需要同时记录“总和”和“数的个数”两个维度。定义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。方案数为dp[i-j][j]。因此状态转移方程为dp[i][j] dp[i-1][j-1] dp[i-j][j]其中i j。 边界条件dp[0][0] 1其他dp[0][j] 0(j0)。def partition_into_k_parts(n, k): dp [[0] * (k 1) for _ in range(n 1)] dp[0][0] 1 for i in range(1, n 1): # j不能超过i也不能超过k 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]4.2 变种二划分成不同正整数的方案数问题将n划分成若干个互不相同的正整数之和的方案数。思路分析 这相当于在完全背包问题中每个数字物品最多只能使用一次即0-1背包的计数问题。 定义dp[j]为凑出总和j且使用的数字都不同的方案数。 初始dp[0] 1。 遍历数字i从1到n但内层循环j需要逆序从n到i0-1背包的标准写法dp[j] dp[j - i](当j i时)。def partition_into_distinct(n): dp [0] * (n 1) dp[0] 1 for i in range(1, n 1): # 逆序更新确保每个数字最多用一次 for j in range(n, i - 1, -1): dp[j] dp[j - i] return dp[n]4.3 变种三划分成奇数/特定集合的方案数问题将n划分成若干个奇数之和的方案数。有趣的是数学上可以证明将n划分成若干不同正整数的方案数等于将n划分成若干奇数的方案数。思路分析 此时我们的“物品”集合不再是1到n而是所有的正奇数1, 3, 5, ...直到不超过n。这仍然是一个完全背包计数问题只是外层循环的i步长为2。def partition_into_odd(n): dp [0] * (n 1) dp[0] 1 for i in range(1, n 1, 2): # 只遍历奇数 for j in range(i, n 1): dp[j] dp[j - i] return dp[n]5. 实战技巧与常见陷阱在实际解题和编码中有一些技巧和陷阱需要特别注意。5.1 初始化是灵魂计数DP中dp[0] 1这个初始化至关重要且容易出错。它的物理意义是“达成0这个状态的方案数为1”通常代表“什么都不选”或“空方案”。在很多变种问题中比如“恰好k个数”dp[0][0]1但dp[0][j0]0需要仔细根据状态定义来确定。5.2 遍历顺序决定问题本质完全背包计数数字可重复使用物品i在外层容量j在内层且正序。0-1背包计数数字不可重复使用物品i在外层容量j在内层且逆序。分组背包或其他根据具体限制调整循环顺序和层数。顺序错了整个问题的含义就变了。这是背包类DP最需要反复确认的点。5.3 模运算下的减法当状态转移方程中包含减法时例如某些容斥原理的DP在取模环境下dp[j] - dp[x]可能会得到负数。正确的处理方式是加上模数后再取模(dp[j] - dp[x] MOD) % MOD。5.4 空间与时间的权衡一维DP是首选。但对于一些复杂的变种如需要记录“个数”、“最大值”、“最小值”等多个维度可能不得不使用二维甚至三维DP。此时要考虑是否可以通过滚动数组优化。例如在“恰好k个数”的变种中dp[i][j]只依赖于dp[i-1][j-1]和dp[i-j][j]其中i-j i所以不能简单优化成一维但可以使用两个一维数组交替滚动。5.5 调试与验证对于计数DP小规模数据的验证极其重要。可以用暴力搜索DFS生成n较小如n10或15时的所有划分方案直接计数与你的DP结果对比。这是检验状态定义和转移方程是否正确的最可靠方法。例如验证基本划分数def brute_force_partition(n): def dfs(remaining, start, path): if remaining 0: result.append(path[:]) return for i in range(start, remaining 1): path.append(i) dfs(remaining - i, i, path) # 注意start传i保证非递减避免重复 path.pop() result [] dfs(n, 1, []) return len(result), result[:10] # 返回总数和前10个方案示例用这个函数的结果去核对你的partition_number(n)可以快速发现错误。6. 从划分数到更一般的计数DP划分数问题是一个完美的跳板。理解了它你就可以去攻克更多经典的计数DP问题整数拆分LeetCode 343要求乘积最大这虽然也是拆分但目标是求最值而非计数思路不同。零钱兑换 IILeetCode 518标准的完全背包计数问题几乎和划分数一模一样只是“物品”硬币面额是给定的一个数组而非连续的1...n。组合总和 IVLeetCode 377注意这个题是顺序不同的序列视为不同组合这其实是求排列数而不是组合数。其状态定义通常是dp[i]表示凑成总和i的排列数转移时外层循环是容量i内层循环是物品nums[j]。这和划分数有本质区别。分割等和子集LeetCode 416这是0-1背包的存在性问题而非计数问题。目标和LeetCode 494给数组中的数添加正负号使得和为target。可以转化为子集和问题是一个经典的0-1背包计数。核心鉴别点当你拿到一个计数问题时先问自己三个问题 (1) 组合无序还是排列有序 - 决定遍历顺序。 (2) 每个元素数字能用几次无限次-完全背包一次-0-1背包有限次-多重背包 - 决定内层循环方向。 (3) 状态需要哪些维度总和、个数、最大值、最小值等 - 决定dp数组的维度和定义。把划分数这个模型嚼碎了这些问题的状态设计和转移方程推导就会变得有章可循。计数DP的难点不在于代码而在于最初那一步——如何设计出一个能天然去重、完备覆盖所有情况的状态。这需要大量的练习和总结而划分数无疑是最好的第一课。