整数分拆

概念

整数分拆（Integer Partition）是指将正整数 $n$ 表示为若干正整数之和的方式数。当限制加数的范围为 $1$ 到 $k$ 时，问题变为：用不超过 $k$ 的正整数之和表示 $n$，有多少种不同的方法。

这是一个经典的组合计数问题，可以转化为 完全背包 DP 来求解。

核心思想

背包 DP 建模

将 $1,2,\dots ,k$ 看作 $k$ 种物品，每种物品可以使用无限次（完全背包），物品 $i$ 的”重量”为 $i$，背包容量为 $n$，求恰好装满背包的方案数。

状态定义：$dp[j]$ 表示用当前可用的物品恰好凑出总和 $j$ 的方案数。

转移方程（完全背包正序枚举）：

$dp[j]=dp[j]+dp[j-i],i=1,2,\dots ,k$

初始条件：$dp[0]=1$（空分拆，即什么都不选是一种方案）。

有序与无序

• 无序分拆（标准整数分拆）：$\{1,2,2\}$ 和 $\{2,1,2\}$ 算同一种。外层枚举物品 $i$，内层枚举容量 $j$。
• 有序分拆（组合数）：顺序不同算不同方案。此时不分层枚举物品，直接对所有 $i$ 同时转移。

大数问题

当 $n$ 和 $k$ 较大时，方案数会非常大，通常需要高精度（大整数）运算或取模。

时间复杂度

$O(nk)$

空间复杂度（滚动数组优化后）：$O(n)$。

适用场景

• 组合计数类问题
• 整数拆分的方案数统计
• 可转化为完全背包的方案计数问题
• 数论中分拆函数 $p(n)$ 的计算