1. 项目概述从整数划分到完全背包的思维跃迁“整数划分”这个问题乍一看是个纯粹的数学组合问题给定一个正整数n有多少种不同的方式可以将其表示为若干个正整数之和例如n5那么55,541,532,5311,5221,52111,511111一共是7种。这个问题在组合数学里历史悠久解法也五花八门从递归、动态规划到生成函数都有涉及。但在算法竞赛和面试中我们更关心的是如何高效、通用地解决它尤其是当n的规模达到几千甚至上万时。Acwing 900题给出的解法其精妙之处在于它完成了一次关键的“思维跃迁”将一个看似与背包无关的整数划分问题完美地映射到了“完全背包求方案数”这个经典的动态规划模型上。这不仅仅是提供了一段可以“抄作业”的代码模板更重要的是传授了一种将陌生问题转化为已知模型的思考方式。对于正在学习动态规划尤其是背包问题的朋友来说理解这个转化过程其价值远超于记住模板本身。它能帮你打通任督二脉以后遇到诸如“零钱兑换方案数”、“数字组合”等问题时都能迅速找到思路。接下来我们就彻底拆解这个“模板”看看它背后的逻辑、实现细节以及那些容易踩坑的地方。2. 核心思路拆解为什么整数划分就是完全背包理解这个问题的核心在于建立正确的“物品”和“容量”概念。我们先回顾一下完全背包问题的经典描述有一个容量为V的背包和N种物品每种物品有无限个第i种物品的体积是v[i]价值是w[i]。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。现在我们把整数划分n的问题进行如下映射背包容量V 就是我们要划分的整数n。我们的目标是“装满”这个容量为n的背包。物品 我们可以使用的“零件”是哪些题目要求是正整数之和。那么最小的正整数是1最大不能超过n本身。因此我们可以认为有n种物品分别是体积为1, 2, 3, ..., n的物品。物品数量 在划分中同一个数字可以重复使用无数次比如511111。这正好对应了完全背包中“每种物品有无限个”的条件。目标 在完全背包中我们通常求的是最大价值。但在这里我们并不关心“价值”我们只关心“能否恰好装满背包”的方案数量。因此这是一个“完全背包求方案数”问题。状态定义 定义f[i][j]为考虑前i种物品即数字1到i恰好组成总和体积为j的方案数。这里i和j都从1开始。状态转移 这是动态规划的精髓。对于当前状态f[i][j]我们考虑数字i的使用情况不使用数字i 那么方案数就等于只使用前i-1种数字组成j的方案数即f[i-1][j]。使用至少一个数字i 如果我们决定使用数字i那么剩下的总和就是j - i。注意因为数字i可以无限使用在使用了这一个i之后我们仍然可以继续使用前i种数字包括i本身来凑剩下的j-i。因此这部分方案数就是f[i][j-i]。将两者相加就得到了经典的状态转移方程f[i][j] f[i-1][j] f[i][j-i]。初始化 当需要组成的和为0 (j0) 时无论考虑前几种数字唯一的方案就是“什么都不选”所以f[i][0] 1对于所有i都成立。这个二维的DP方程已经揭示了问题的本质。但在实际编码中为了追求极致的空间效率从O(n^2)降到O(n)我们几乎总是使用滚动数组进行优化。3. 一维优化与代码模板详解二维DP的f[i][j]只依赖于f[i-1][j]和f[i][j-i]。观察可知f[i-1][j]是上一轮i-1的结果而f[i][j-i]是本轮已经计算过的、更小的j的结果。这完美符合滚动数组优化的条件。我们定义一维数组f[j]表示恰好组成总和j的方案数。在每一轮循环考虑数字i中我们如何更新它f[i-1][j]对应优化前的f[j]在本轮i的循环中还未被覆盖保存的是上一轮i-1的结果。f[i][j-i]对应优化后的f[j-i]因为j-i j当我们从小到大遍历j时f[j-i]已经在本次循环中被更新过了它代表的是“考虑了数字i后组成j-i的方案数”。因此优化后的一维转移方程为f[j] f[j] f[j-i]。其中等号右边的f[j]是“不使用i”的方案数旧值f[j-i]是“使用至少一个i”的方案数新值。初始化f[0] 1表示组成0的方案数为1空集。下面给出最经典的C模板代码并附上详细注释#include iostream using namespace std; const int N 1010, MOD 1e9 7; // 定义常量N为n的最大范围MOD是取模值 int n; int f[N]; // f[j] 表示恰好组成总和j的方案数 int main() { cin n; f[0] 1; // 初始化组成0的方案数为1什么都不选 // 外层循环枚举“物品”即数字 i (从1到n) for (int i 1; i n; i) { // 内层循环枚举“背包容量”即要组成的和 j (从i到n) // 注意j从i开始因为如果ji那么数字i根本用不上f[j]保持不变即可 for (int j i; j n; j) { // 核心状态转移方程 // f[j] (新) f[j] (旧不使用i的方案) f[j-i] (使用至少一个i的方案) f[j] (f[j] f[j - i]) % MOD; // 每一步都取模防止溢出 } } cout f[n] endl; // 输出恰好组成总和n的方案数 return 0; }关键点解析循环顺序 外层循环是物品i内层循环是容量j并且j是从小到大遍历。这是完全背包一维优化的标准特征与01背包内层从大到小有本质区别。从小到大的遍历保证了在计算f[j]时f[j-i]已经考虑了当前物品i从而实现了物品的无限次选取。内层循环起点j从i开始。这是一个有效的剪枝。因为当j i时当前数字i比要组成的和j还大不可能被使用所以f[j]保持原值即只使用前i-1个数字的方案数。从i开始循环避免了无用的判断和计算。取模操作 方案数可能非常巨大题目通常要求对1e97取模。务必在每次加法后立即取模而不是最后才取模否则中间结果可能溢出int甚至long long的范围。4. 与其它解法的对比与深度思考理解了这个完全背包模型后我们不妨看看它和其他常见解法的关系这能加深对问题本质的理解。4.1 与“另一种DP定义”的对比还有一种常见的DP定义是g[i][j]表示总和为i并且恰好由j个数字组成的方案数。其转移方程考虑最后一个数字的大小g[i][j] g[i-1][j-1] g[i-j][j]。这个方程也有其组合意义但它最终求解需要将g[n][1]到g[n][n]求和其状态是O(n^2)且不如完全背包模型直观通用。完全背包模型直接瞄准了“方案总数”思维链条更短。4.2 与“零钱兑换II”问题的关联LeetCode上有经典的“零钱兑换II”问题给定不同面额的硬币和一个总金额求可以凑成总金额的硬币组合数。你会发现它就是整数划分的一个“子集”。整数划分中物品是1到n的所有数字而零钱兑换中物品是给定的硬币数组coins。如果coins数组恰好是[1, 2, 3, ..., n]那么两个问题就完全等价了。因此Acwing 900的模板其实就是零钱兑换II问题在硬币面额为连续整数时的特解同时也是通解只需将外层循环的i遍历coins数组即可。掌握这个模板相当于同时掌握了两个高频考点。4.3 关于“顺序不同视为同一种方案”这是本题的一个关键也是容易产生困惑的点。我们的状态转移f[j] f[j-i]为什么不会导致312和321被算作两种不同方案 这是因为我们的外层循环是“物品”数字。在动态规划的过程中我们是在按顺序考虑是否使用每个数字。当我们固定了物品的考虑顺序先考虑1再考虑2再考虑3...那么一个方案{1, 2}只会以一种特定的“生成路径”被构造出来例如在考虑数字1时用了考虑数字2时用了而不会出现先通过数字2再通过数字1生成同一种集合的情况。这本质上是组合数而非排列数。如果题目要求考虑顺序那就变成了另一种模型爬楼梯问题。5. 常见问题、调试技巧与扩展5.1 初始化f[0] 1的理解这是动态规划中常见的“边界”或“种子”。f[0]1表示“用任何数字组合出总和0有1种方法什么都不选”。它在状态转移中起着基石作用。例如当j i时f[j] f[j] f[0]f[0]1就代表了“只选一个当前数字i”这种方案。5.2 结果为什么是f[n]而不是累加我们的状态定义是“恰好组成总和j”所以最终答案就是恰好组成n的方案数f[n]。有些题目可能问“不超过总和n的方案数”那答案就需要对f[0]到f[n]求和。务必仔细审题。5.3 如何打印具体的划分方案DP求的是方案数要输出所有具体方案就需要用回溯法DFS。我们可以记录下DP的路径但更常见的做法是直接写一个DFS函数参数包含当前剩余的和remain、当前起始数字start为了避免重复保证划分是递增或递减的以及当前已选择的列表。当remain 0时就输出一个方案。这种方法虽然不能直接利用DP数组加速但思路清晰。// 打印所有具体划分方案的DFS示例非DP部分 vectorint path; void dfs(int remain, int start) { if (remain 0) { // 打印path for (int x : path) cout x ; cout endl; return; } for (int i start; i remain; i) { path.push_back(i); dfs(remain - i, i); // 注意下一个start是i保证不递减去重 path.pop_back(); } } // 调用dfs(n, 1);5.4 模运算的坑MOD 1e9 7是一个质数这在取模运算中很好。但要注意在C中1e97是double类型赋值给int常量没问题。但在一些计算中如果涉及负数取模可能会得到负数结果C的%是取余运算。为了保证结果非负可以写成(f[j] f[j-i]) % MOD因为两者都是非负的所以结果也是非负的。更稳健的写法是(f[j] f[j-i]) % MOD。5.5 如果n很大比如 5000怎么办上述DP的时间复杂度是O(n^2)空间是O(n)。当n达到10^4或10^5时O(n^2)的算法就会超时。此时整数划分问题通常需要更高级的数学方法如五边形数定理Euler‘s Pentagonal Number Theorem可以在O(n*sqrt(n))的时间内求解。但这已经超出了算法竞赛初学者的范围也是完全背包模型无法解决的极限。对于面试和大多数笔试掌握O(n^2)的DP解法已经足够。5.6 模板的泛化应用这个模板的灵魂在于“完全背包求方案数”。一旦你识别出某个问题具有以下特征有若干种“元素”物品每种可以无限使用。需要组合这些元素来达到一个“目标总量”背包容量。求解的是达成目标的不同组合的数量方案数。 那么你就可以尝试套用这个模型。只需根据问题定义好“物品体积”和“背包容量”初始化f[0]1然后写两层循环外层遍历物品内层从小到大遍历容量状态转移为f[j] f[j-vol[i]]。6. 实战演练与变种思考为了真正掌握我们脱离“连续数字”这个特例看一个更一般的变种假设现在不是用1~n的所有数字而是只能用给定的一个正整数集合S中的数字每个数字无限使用来划分整数n求方案数。这就是LeetCode 518 “零钱兑换II”的完全体。解法几乎一模一样只需将外层循环的i从遍历1~n改为遍历集合S中的每个数字coin。int coinChangeWays(vectorint coins, int amount) { vectorint f(amount 1, 0); f[0] 1; for (int coin : coins) { // 外层遍历给定的硬币/数字 for (int j coin; j amount; j) { // 内层从小到大遍历金额 f[j] f[j - coin]; // f[j] % MOD; // 如果需要取模 } } return f[amount]; }另一个变种是考虑“限制划分中数字的个数”或“限制最大数字”。例如求将n划分成恰好k个正整数的方案数。这需要增加一维状态f[i][j][k]复杂度变为O(n^3)但核心思想仍是背包。或者求划分中所有数字都不超过m的方案数这其实等价于用1~m的数字划分n只需将我们模板中的外层循环终点从n改为m即可。最后分享一个我个人的调试心得当你对DP方程不确定时不要急于写优化后的一维代码。先用最朴素的二维数组f[i][j]把DP表打出来手动模拟n5这样的小例子观察每个格子是如何由之前的格子计算出来的。这个过程能让你对状态转移的理解变得无比清晰。比如画出f[i][j]在i, j从0到5的表格对照着公式f[i][j] f[i-1][j] f[i][j-i]去填你会直观地看到“不用i”和“用i”的贡献分别来自哪里。理解透彻后再推导出一维优化就会觉得理所当然而不是死记硬背循环顺序。