写笔试题有个很有意思的现象越是看起来简单的数学题越容易把人卡在笔试现场。正整数划分就是典型代表。题目往往只有一句话“把一个正整数拆成若干个正整数之和求方案数。”看完题目觉得不难真到动手写状态转移方程的时候脑子里却像打了结一样半天理不清“到底怎么去重”“要不要考虑顺序”“复杂度能不能过”。我见过好几个基本功不错的同学在笔试里栽在这道题上有人敲了半个小时的暴力搜索结果超时有人写对了状态方程但没处理取模还有人忽略了“划分”和“拆分”的口径差异样例都过不去。所以这篇文章不打算只贴一段标准答案而是把正整数划分从定义、经典解法、变体题型到笔试现场的应试策略完整拆一遍。无论你是在准备春招秋招还是日常刷题巩固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”只能出现一次所以 22 不合法最终只有 2 种。指定最大可用数字。比如只能用不超过 2 的数字划分 4方案为 22、211、1111共 3 种。指定划分成恰好 k 个数。比如把 4 拆成恰好 2 个数只有 31 和 22 两种。这些限制条件看起来只是换了个说法但状态转移方程的差异很大。笔试中如果读题不仔细很容易套错模板。我建议拿到题的第一时间就问自己三个问题数字能不能重复要不要输出具体方案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 时返回 0n 0 时返回 1只有一种方案什么都不拆递归出口m 0 时返回 0没有可用数字。这种写法能直接通过小规模数据但 n 稍大一点就会指数爆炸。因为 f(n, m) 会被反复调用大量重复子问题。所以下一步自然想到加备忘录也就是记忆化搜索。不过笔试环境里我更建议直接写DP数组毕竟递归有栈风险Python 还不一定开得了很大递归深度。2.2 二维DP的状态设计与转移方程从递归式可以直接翻译成二维DP。令 dp[i][j] 表示“用不超过 j 的正整数组成 i 的方案数”初始化 dp[0][j] 1dp[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 就会开始吃内存这时候需要优化。计算一下n5000 时二维数组有 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]三行核心代码题目就解完了。很多人在这里有个疑问为什么外层是数字、内层是容量反过来行不行不行。如果外层遍历容量、内层遍历数字会出现同一个容量的更新过程中反复计算多种数字组合顺序导致把 13 和 31 当成了两种方案。笔试时间紧这种方向性错误特别隐蔽我建议把“外层物品、内层容量、正序更新”这个口诀背下来。如果题目改成“每个数字最多使用一次”那就是 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) 1n 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, 11 n 3 - 3 3, 21, 111 n 4 - 5 4, 31, 22, 211, 1111 n 5 - 7 5, 41, 32, 311, 221, 2111, 11111这个序列读者可能已经认出来了就是整数划分的经典序列 1, 2, 3, 5, 7, 11, 15, 22...。记住前几个值可以快速验证代码方向。如果 n5 得到 6 而不是 7说明转移中漏掉了某种情况最常见的是漏掉了“包含最大数字本身的方案”。边界测试除了 n 很小的情况还要测 n 等于模数附近的情况确保取模没有溢出后出现负数。C 里如果只在最后取模中间结果溢出 int你甚至测不出错误答案直接变成负数或乱值。所以每步取模不是形式是防线。5.3 多解法对比与面试官沟通思路笔试中的在线编程题往往只认最终结果但如果是在面试现场做白板题沟通策略就完全不同。我建议按顺序呈现三种解法先给搜索思路说明“分解为选或不选当前最大数字 m”的递归结构让面试官知道你理解问题的本质。再给二维DP优化说明如何用记忆化去除重复计算复杂度 O(n^2)。最后写成完全背包的一维代码顺手展示空间优化能力。这个顺序本身就是“暴力 - 优化 - 状态压缩”的完整演进路径。面试官最反感的是上来就写一维代码解释不清为什么内层正序、为什么外层是物品。你如果能把从递归到背包的推导过程讲清楚已经赢了大半。6. 常见问题与排查技巧实录6.1 笔试中容易踩的坑清单问题原因解决方式结果比预期大两倍以上把顺序不同的拆分记成了多种方案检查外层是否遍历物品内层是否正序小样例正确大数据超时使用了二维数组且查询范围过大或未优化改成一维复杂度 O(n^2) 即可结果出现负数C 中间结果溢出 int所有加法后立即取模使用 long long输出方案包含重复组合递归回溯时 max_used 参数传错确保下一次递归的最大数字为当前数字本身“恰好 k 个数”题目套用普通划分公式没有识别出题目中的“恰好”限定使用 f(n,k)f(n-1,k-1)f(n-k,k) 或增加一维背包Python 大数据递归栈溢出使用递归实现搜索改用迭代DP或先 sys.setrecursionlimit这些问题我都见过不止一次。尤其是“结果比预期大”这种错误样例数据里往往不容易暴露跑到 n10 左右才能看出来。所以笔试时宁可多花十几秒手算 n5 和 n6 的期望值也不要省这个验证。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 还是在考组合数学的思维。最后再分享一个小技巧是我自己刷题时总结的如果笔试环境允许同时开着暴力程序和优化程序做交叉验证哪怕只测到 n20也足以发现绝大多数的状态转移错误。真正的高手不是不会犯错而是能用更短的时间发现错误并修正。把这套“自查 - 验证 - 复盘”的方法用到极致正整数划分不仅能稳拿分还能成为面试展示思维过程的加分项。
