正整数划分经典解法：从动态规划到完全背包的笔试题实战

写笔试题有个很有意思的现象：越是看起来简单的数学题，越容易把人卡在笔试现场。正整数划分就是典型代表。题目往往只有一句话：“把一个正整数拆成若干个正整数之和，求方案数。”看完题目觉得不难，真到动手写状态转移方程的时候，脑子里却像打了结一样，半天理不清“到底怎么去重”“要不要考虑顺序”“复杂度能不能过”。

我见过好几个基本功不错的同学在笔试里栽在这道题上，有人敲了半个小时的暴力搜索结果超时，有人写对了状态方程但没处理取模，还有人忽略了“划分”和“拆分”的口径差异，样例都过不去。所以这篇文章不打算只贴一段标准答案，而是把正整数划分从定义、经典解法、变体题型到笔试现场的应试策略完整拆一遍。无论你是在准备春招秋招，还是日常刷题巩固DP基础，都可以把这篇文章当作一份能直接“抄作业”的实战笔记。

1. 题目到底在问什么：正整数划分的两种常见口径

1.1 无限制划分：可以重复使用数字

先看最经典的版本。给定正整数 n，将 n 拆成若干个正整数之和，顺序无关，数字可以重复，求拆法总数。比如 n = 4 时：

4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1

一共 5 种。注意“顺序无关”是整数划分问题的核心约定，3 + 1 和 1 + 3 算同一种方案。这个约定直接决定了状态设计的方向：我们只能让非降序排列的拆法计入答案，否则要去重就非常麻烦。

这种“每个数字可以用任意多次”的口径，恰好对应了后面会讲到的完全背包模型。笔试里如果没有额外说明，默认都是指这种无限制正整数划分。

1.2 限制性划分：不可重复与数字受限

实际考题经常在无限制划分基础上加约束，常见的包括：

• 每个数字最多使用一次。此时 n = 4 的方案就变成：4、3 + 1、2 + 2 中“2”只能出现一次所以 2+2 不合法，最终只有 2 种。
• 指定最大可用数字。比如只能用不超过 2 的数字划分 4，方案为 2+2、2+1+1、1+1+1+1，共 3 种。
• 指定划分成恰好 k 个数。比如把 4 拆成恰好 2 个数，只有 3+1 和 2+2 两种。

这些限制条件看起来只是换了个说法，但状态转移方程的差异很大。笔试中如果读题不仔细，很容易套错模板。我建议拿到题的第一时间就问自己三个问题：数字能不能重复？要不要输出具体方案？n 的取值范围是多少？这三个问题的答案直接决定了选哪套解法。

1.3 笔试里常见的考法包装

正整数划分在笔试题里很少“裸考”，通常会被包装成其他形式。最常见的是“上台阶变体”：“有一级、二级、三级台阶，爬 n 级台阶有多少种爬法”，这本质上是把步长集合固定为 {1,2,3} 的划分问题。还有“换零钱”：“现有若干面额，凑出总额 n 有多少种凑法”，这就是带面额限制的划分问题。另外还有“括号生成”“矩阵链乘分拆”这些看起来完全不同的问题，内核对正整数划分也是一脉相通的。

理解了考法包装，你就知道为什么这道题值得花时间死磕。它不是一个孤立题目，而是一整类DP题目的地基。把这套“限制条件如何转化为状态维度”的思考方式练熟，后面遇到任何变形都能快速反应。

2. 从暴力搜索到动态规划：解法推导全过程

2.1 朴素搜索的递归结构与剪枝空间

先别急着写DP，从暴力搜索入手反而能帮助你理解状态的含义。设计递归函数 f(n, m) 表示“用不超过 m 的正整数组成 n 的方案数”。为什么非要带上 m 这个限制？因为它帮我们保证非降序，避免重复计数。递推关系是：

f(n, m) = f(n, m - 1) + f(n - m, m)

这个公式怎么理解？把方案分成两类：一类完全不用数字 m，方案数是 f(n, m - 1)；另一类至少用一个 m，那就先拿出一个 m，剩余部分继续用不超过 m 的数字去凑，方案数是 f(n - m, m)。这样分类是完备且互斥的。

递归边界有三个：

• n < 0 时返回 0；
• n == 0 时返回 1（只有一种方案：什么都不拆，递归出口）；
• m == 0 时返回 0（没有可用数字）。

这种写法能直接通过小规模数据，但 n 稍大一点就会指数爆炸。因为 f(n, m) 会被反复调用，大量重复子问题。所以下一步自然想到加备忘录，也就是记忆化搜索。不过笔试环境里我更建议直接写DP数组，毕竟递归有栈风险，Python 还不一定开得了很大递归深度。

2.2 二维DP的状态设计与转移方程

从递归式可以直接翻译成二维DP。令 dp[i][j] 表示“用不超过 j 的正整数组成 i 的方案数”，初始化 dp[0][j] = 1，dp[i][0] = 0，然后按 i 从小到大、j 从小到大转移：

dp[i][j] = dp[i][j - 1] + (i >= j ? dp[i - j][j] : 0)

这里第二项的语义和递归式完全一致：如果 i >= j，说明可以用一个 j，既然用了 j，剩下的 i - j 依然允许用不超过 j 的数字继续拆。

二维转移的时间复杂度是 O(n^2)，空间复杂度也是 O(n^2)。n 在 1000 以内的话完全没问题，n 到 5000 就会开始吃内存，这时候需要优化。计算一下：n=5000 时，二维数组有 2500 万个元素，如果每个元素用 int 存储，内存约 100 MB，笔试环境很容易超限。所以掌握一维优化是必要的。

2.3 优化方向：一维滚动数组与完全背包映射

一维优化的核心是把“数字可以用任意多次”翻译成完全背包。从另一种视角重新描述问题：有无限多个正整数 1、2、3、…、n，每个数字是“物品”，数字本身是“重量”，要恰好装满容量为 n 的背包，问方案数。

完全背包的经典写法是：外层循环遍历物品种类，内层循环正序遍历容量。对应到本题，就是外层枚举“允许使用的最大数字 j”，内层从 j 递增到 n，执行 dp[i] += dp[i - j]。这里要解释清楚为什么内层必须正序：正序遍历意味着同一个 j 可以被多次使用，刚好符合“数字可以重复”的要求。

def partition_count(n: int) -> int: dp = [0] * (n + 1) dp[0] = 1 for j in range(1, n + 1): # 物品：数字 j for i in range(j, n + 1): # 容量：从 j 到 n dp[i] += dp[i - j] return dp[n]

三行核心代码，题目就解完了。很多人在这里有个疑问：为什么外层是数字、内层是容量，反过来行不行？不行。如果外层遍历容量、内层遍历数字，会出现同一个容量的更新过程中反复计算多种数字组合顺序，导致把 1+3 和 3+1 当成了两种方案。笔试时间紧，这种方向性错误特别隐蔽，我建议把“外层物品、内层容量、正序更新”这个口诀背下来。

如果题目改成“每个数字最多使用一次”，那就是 0/1 背包，唯一的区别是内层循环改成正序为倒序：

for j in range(1, n + 1): for i in range(n, j - 1, -1): # 倒序，保证每个 j 只使用一次 dp[i] += dp[i - j]

这两种背包模型的对比，是笔试考察的高频区分点。你在写代码前一定要确认题目到底允许数字重复还是不允许，一旦写错方向，样例能过都不奇怪，测试数据一多就崩。

3. 核心实现与笔试现场的边界处理

3.1 一维DP完整代码与取模细节

实际笔试里 n 经常会给到 10^4 甚至更大，输出要求对某个大质数取模，最常见的是 1_000_000_007。加取模的完整代码很简单：

MOD = 10**9 + 7 def partition_count(n: int) -> int: dp = [0] * (n + 1) dp[0] = 1 for j in range(1, n + 1): for i in range(j, n + 1): dp[i] = (dp[i] + dp[i - j]) % MOD return dp[n]

取模要养成分步进行的习惯，不要等最后统一取模。因为中间结果可能早就超过 Python 的任意精度范围，虽然在 Python 里不会溢出，但大整数运算会拖慢速度，在 C++ 里更是直接溢出 int。C++ 版本的写法也要注意用 long long，所有加法后立即取模：

const int MOD = 1e9 + 7; long long dp[100005]; for (int j = 1; j <= n; ++j) { for (int i = j; i <= n; ++i) { dp[i] = (dp[i] + dp[i - j]) % MOD; } }

还有一点容易被忽略：dp[0] = 1 这个初始条件看上去有点违和，但它是递归边界 n == 0 时候的唯一方案，翻译成背包语言就是“容量为 0 时什么都不装，恰有一种方案”。很多面试官特别喜欢追问“为什么 dp[0] 是 1”，如果你能说出这层含义，印象分会高不少。

3.2 输出具体划分方案时的路径回溯写法

有些拔高题不满足于求方案数，还要求打印所有划分方案。这时候需要把二维DP保留下来，然后在回填完整后从 dp[n][n] 开始回溯。核心思想是：如果 dp[i][j] 的来源包含“使用 j”，也就是 i >= j 且取了第二项，就输出一个 j，然后转移到 dp[i - j][j]；否则转移到 dp[i][j - 1]。

以记忆化搜索实现输出方案会更直观。定义 dfs(i, max_used, path) 表示当前剩余为 i、允许使用的最大数为 max_used，遍历候选数字 j 从 min(max_used, i) 往下走到 1，递归去生成后续部分。这种写法比较适合 n <= 30 左右的场景，因为方案数本身是指数级增长，输出全部方案无论如何都跑不大。

def generate_partitions(n: int): res = [] def dfs(remain: int, max_used: int, path: list): if remain == 0: res.append(path[:]) return for j in range(min(max_used, remain), 0, -1): path.append(j) dfs(remain - j, j, path) # 下一次能用到的最大数字不能超过当前 j path.pop() dfs(n, n, []) return res

注意这里 dfs 里传入的 max_used 是当前实际选取的数字 j，而不是 remain - j 的 min。这样才能保证后续的数字都不大于当前数字，整个序列按非升序生成，天然去重。如果你不小心把 max_used 写成 remain，就会生成大量顺序不同但内容相同的方案。

3.3 复杂度分析与笔试中的参数选择

一维DP的时间复杂度是 O(n^2)，空间复杂度是 O(n)。n = 10^4 时内层循环大约要跑 5000 万次，Python 会接近 1 秒到 2 秒，存在超时风险。C++ 则很轻松。如果笔试环境限时 1 秒、语言是 Python，建议先观察数据范围：n <= 5000 时无脑跑没问题；n 更大但要求取模，可以尝试用“整数划分的三角数优化”，把复杂度压到 O(n√n) 级别。

整数划分存在一个很经典的优化：因为任何大于 √n 的数字在一组划分中使用次数不超过 √n 次，所以可以分两段考虑。不过这种优化在笔试中属于加分项，不作为必会内容。我的建议是先把 O(n^2) 写对、写稳，留出时间做后面的题，而不是冒险写一个容易出错的高级优化。笔试本质是拿分游戏，O(n^2) 能拿到的分数通常是 80%~100%，已经是很好的结果。

4. 高频变形与举一反三：笔试出现的多种考法

4.1 恰好拆成 k 个数

这是目前笔试中出现频率最高的变形之一。设 f(n, k) 表示把 n 拆成恰好 k 个正整数之和的方案数，要求顺序无关。推导思路是看划分中是否包含数字 1：

• 包含 1：先拿出一个 1，剩下 n - 1 需要拆成恰好 k - 1 个数，方案数是 f(n - 1, k - 1)。
• 不包含 1：既然没有 1，那么每个数都至少是 2。把每个数都减去 1，就得到 n - k 拆成恰好 k 个数的问题，方案数是 f(n - k, k)。

因此状态转移为：

f(n, k) = f(n - 1, k - 1) + f(n - k, k)

边界条件是 k == 1 时 f(n, 1) = 1，n == k 时 f(n, k) = 1（每个数都是 1）。二维循环做下来，复杂度同样是 O(nk)。

这个推导过程一定要亲手推一遍。我面试过不少人，能报出公式 f(n,k) = f(n-1,k-1) + f(n-k,k)，但问一句“第二项为什么不是 f(n-k,k-1)”就卡住了。关键就在于“所有数减 1”等价于从划分中分出一层，减完之后方案数对应的是 n-k 拆成 k 个非负整数（原本每个数减 1 后可以是 0），但因为我们讨论的是正整数划分的对应关系，所有数减 1 后仍然恰好 k 个数，且每个数可以为 0，此时需要再处理 0 的边界。更严谨的表述是：无 1 划分时，所有数都 >= 2，减 1 后所有数 >= 1，所以从 f(n-k, k) 继承。

4.2 奇偶受限与数字上界受限的变式

有些题目限制划分中的数字必须全部是奇数，或者全部是偶数。这种限制本质上是一样的：修改物品集合即可。

比如限制只用奇数，就把外层循环写成for j in range(1, n + 1, 2)；限制只用偶数则for j in range(2, n + 1, 2)。它们背后的模型没变，变的只是物品集合。千万别把这种题目当成新题来推公式，那样浪费时间还容易出错。

限制数字上界的版本对应的是“换零钱”问题：手上只有面额 1 到 m 的硬币，每种无限量，凑出 n 的方案数。状态转移不变，外层循环只遍历到 m，即：

for j in range(1, min(m, n) + 1): for i in range(j, n + 1): dp[i] += dp[i - j]

这类题常常伪装成“机器人上台阶”“铺砖块”等场景，核心一望即知是划分模型。识别这种“换皮不换核”的能力，比会背十道题更重要。

4.3 生成函数视角：不仅会做，还能说清楚

如果你想在笔试后的面试环节充分展示自己，可以提一句生成函数。无限制正整数划分的生成函数是：

G(x) = (1 + x + x^2 + ...)(1 + x^2 + x^4 + ...)(1 + x^3 + x^6 + ...)... = 1 / ((1 - x)(1 - x^2)(1 - x^3)...)

展开后每一项的系数就是对应 n 的划分方案数。生成函数的优势在于方便分析复杂度，也能统一理解很多看似不同的划分限制：比如“数字不能重复”对应的因子是 (1 + x^j)，而不是无穷等比级数。

我个人建议，生成函数不要为了炫技硬讲。只有在面试官明显往数学方向追问时再展开，而且一定要能写出实际推导过程，否则很容易被认为“背答案”。笔试里写代码拿分才是硬道理。

5. 笔试现场实战策略与时间分配

5.1 拿到题目的第一分钟做什么

正整数划分这道题，笔试图不给任何样例都有可能。我拿到题会做四件事：

• 先手写 n = 4、n = 5 的划分，把答案列出来，确认自己对“顺序无关”的理解。
• 再看一眼题面有没有“恰好”“不超过”“至少”“互不相同”这类限定词。
• 看 n 的数据范围，决定用二维还是用优化到一维的代码。
• 确认取模要求，有没有模数，模数是什么。

这四件事通常在 30 秒内完成。很多人拿到题就开始敲代码，结果敲到一半发现“数字能不能重复”理解错了，整个代码推翻重来，这在笔试里非常致命。先花 30 秒确认题意，比盲目抢时间划算得多。

5.2 样例过不过与边界测试的优先级

写完代码先不要急着跑大数据，用下面几个小数据自查：

n = 1 -> 1 n = 2 -> 2 （2, 1+1） n = 3 -> 3 （3, 2+1, 1+1+1） n = 4 -> 5 （4, 3+1, 2+2, 2+1+1, 1+1+1+1） n = 5 -> 7 （5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1）

这个序列读者可能已经认出来了，就是整数划分的经典序列 1, 2, 3, 5, 7, 11, 15, 22...。记住前几个值可以快速验证代码方向。如果 n=5 得到 6 而不是 7，说明转移中漏掉了某种情况，最常见的是漏掉了“包含最大数字本身的方案”。

边界测试除了 n 很小的情况，还要测 n 等于模数附近的情况，确保取模没有溢出后出现负数。C++ 里如果只在最后取模，中间结果溢出 int，你甚至测不出错误，答案直接变成负数或乱值。所以每步取模不是形式，是防线。

5.3 多解法对比与面试官沟通思路

笔试中的在线编程题往往只认最终结果，但如果是在面试现场做白板题，沟通策略就完全不同。我建议按顺序呈现三种解法：

• 先给搜索思路，说明“分解为选或不选当前最大数字 m”的递归结构，让面试官知道你理解问题的本质。
• 再给二维DP优化，说明如何用记忆化去除重复计算，复杂度 O(n^2)。
• 最后写成完全背包的一维代码，顺手展示空间优化能力。

这个顺序本身就是“暴力 -> 优化 -> 状态压缩”的完整演进路径。面试官最反感的是上来就写一维代码，解释不清为什么内层正序、为什么外层是物品。你如果能把从递归到背包的推导过程讲清楚，已经赢了大半。

6. 常见问题与排查技巧实录

6.1 笔试中容易踩的坑清单

这些问题我都见过不止一次。尤其是“结果比预期大”这种错误，样例数据里往往不容易暴露，跑到 n=10 左右才能看出来。所以笔试时宁可多花十几秒手算 n=5 和 n=6 的期望值，也不要省这个验证。

6.2 测试数据自造的技巧

笔试环境不给全部测试数据，但你可以自己生成一份对照表来验证程序正确性。我用 Python 时会先写一个极度暴力但绝对正确的程序：直接生成所有组合，去重后计数。然后把 n 从 1 到 20 的结果打印出来，和 DP 程序的结果逐项对比。

def brute_force(n: int) -> int: res = [] def dfs(remain: int, start: int, path: list): if remain == 0: res.append(path[:]) return for j in range(start, remain + 1): path.append(j) dfs(remain - j, j, path) path.pop() dfs(n, 1, []) return len(res)

这个暴力函数可以保证正确性，因为它枚举了所有非降序可能。用它与优化代码跑同样的 n，如果所有结果一致，那核心逻辑基本可信。这个“双写验证”的习惯，是刷题时代留下来的，到了真实笔试更好用。

6.3 面试追问环节的常见问题

笔试通过后进入面试，面试官十有八九会追问这道题。我整理过几个高频追问：

• 为什么 dp[0] = 1？答：表示容量为 0 时一种方案都不放，是递归基。
• 如果 n 很大，比如 10^6，怎么做？答：引入三角数优化或五边形数定理加速计算，方案数增长也极快。
• 假如要求输出第 k 种划分，怎么处理？答：可以先预处理 dp，再按字典序逐位确定当前位数字。
• 和“爬楼梯”的区别是什么？答：爬楼梯按排列计数，顺序不同算不同方案；划分按组合计数，顺序无关。

最后一个问题尤其值得提前想清楚。爬楼梯 f(n) = f(n-1) + f(n-2) 本质是排列模型，而正整数划分是组合模型，两者虽然都用一维DP，但转移来源和语义完全不同。面试官问这个，就是在考察你是否真正理解模型，而不只是记住代码。

7. 刷题路径与扩展思考

正整数划分的经典刷题路径，我推荐按“一维背包 -> 恰好 k 个数 -> 受限集合 -> 输出方案 -> 大数优化”的顺序来练。前四步对应笔试高频考点，最后一步用于面试加分。在某个刷题平台上把这几类题目各做三道，基本就能形成肌肉记忆。

我个人在实际操作中的体会是：这道题最容易出错的地方不是算法本身，而是读题阶段的“模型误判”。很多同学看到“上台阶”“凑硬币”就走爬楼梯或完全背包模板，忽略了“顺序无关”这个关键约束。做题做多了之后，我开始养成一个习惯：不论题目包装成什么样，先在草稿纸上把样例手算一遍，用最朴素的方式列出所有合法组合，再动手设计状态。这个习惯帮我避开了至少一半的“模型误判”类错误。

如果你时间充裕，还可以再深挖一层：正整数划分方案数本身是一个增长极快的数列，n 到 50 时方案数已经超过 20 万，n 到 100 时超过 1.9 亿。这从另一个角度解释了为什么 30 以上的 n 基本不可能要求输出全部方案，因为输出本身就是指数级的工作量。理解了这个增长规律，你就能判断题目究竟是在考 DP 还是在考组合数学的思维。

最后再分享一个小技巧，是我自己刷题时总结的：如果笔试环境允许，同时开着暴力程序和优化程序做交叉验证，哪怕只测到 n=20，也足以发现绝大多数的状态转移错误。真正的高手不是不会犯错，而是能用更短的时间发现错误并修正。把这套“自查 -> 验证 -> 复盘”的方法用到极致，正整数划分不仅能稳拿分，还能成为面试展示思维过程的加分项。