LeetCode 补充题 143. 整数的 k 项无序划分计数
题目描述
牛客原题： ✅ 补充题 143. 整数的 k 项无序划分计数
给定正整数
n和k，将n分成k个非空正整数部分，不同排列算同一种分法。返回方案数对
1000000007取模的结果。
示例 1：
输入：
n = 7, k = 3
输出：4
解释： 四种分法为1+1+5、1+2+4、1+3+3、2+2+3；相同部分的不同排列不另计。
提示：
-
n、k均为正整数。 - 每份必须为正整数，不同排列视为同一种分法。
- 答案对
1000000007取模。
题意分析
不同排列只算一种，所以不能逐个位置选择数字来计数，否则同一组整数会因顺序不同被重复统计。按照是否包含 1 划分所有方案，能得到互斥且覆盖完整的两类子问题。
每类都通过一个可逆变换对应更小规模的无序划分：含 1 时删去一个 1，不含 1 时每份减去 1。由此推导递推，而不是套用有序组合数公式。
解法：按是否含 1 分类的整数划分 DP
核心思路
[!blue]
先定义二维含义：
F(sum, parts)表示把总和sum分成parts个无序正整数的方案数。按是否包含 1，把所有方案分成互不重叠的两类：
- 含有 1：删去其中一个 1，剩下的方案为
F(sum-1, parts-1)。因为不区分顺序，多个 1 不会带来多个删除位置的计数。- 每份都至少为 2：给每一份减去 1，剩下的方案为
F(sum-parts, parts)。所以两类相加即可。代码的
previous保存上一种份数，current保存当前份数；第二项来自当前行更小的总和，因此sum必须递增。边界F(0,0)=1表示空划分，parts > sum时没有正整数划分。例如把 5 分成 2 份，含 1 的只有
[1,4]；不含 1 的[2,3]每项减一后对应把 3 分成 2 份的[1,2]，两类各一，共两种。
解题步骤
- k>n 时不可能分成 k 个正数，立即返回 0。
- 初始化 0 份构成总和 0 的方案数为 1。
- 按份数递增，当前总和递增，累加含 1 与全部至少 2 两类方案。
- 每次取模，最后返回 k 份组成 n 的状态。
代码实现
class Solution {
public int partitions(int n, int k) {
if (k > n) {
return 0;
}
int mod = 1_000_000_007;
int[] previous = new int[n + 1];
previous[0] = 1;
for (int parts = 1; parts <= k; parts++) {
int[] current = new int[n + 1];
for (int sum = parts; sum <= n; sum++) {
current[sum] = (previous[sum - 1] + current[sum - parts]) % mod;
}
previous = current;
}
return previous[n];
}
}
func partitions(n, k int) int {
if k > n {
return 0
}
const mod = 1_000_000_007
previous := make([]int, n+1)
previous[0] = 1
for parts := 1; parts <= k; parts++ {
current := make([]int, n+1)
for sum := parts; sum <= n; sum++ {
current[sum] = (previous[sum-1] + current[sum-parts]) % mod
}
previous = current
}
return previous[n]
}
复杂度分析
- 时间复杂度：$O(nk)$。
- 空间复杂度：额外空间 $O(n)$。
关键点总结
[!green]
含 1 的方案删除一个 1；不含 1 的方案给每份减一。两类互斥且完整，不需要枚举不同排列。
易错点总结
[!yellow]
不是有序组合数；0份只组成总和0；当前层必须按sum递增。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 518. 零钱兑换 II | 中等 | 同样不区分排列顺序，本题还固定份数，需要额外保存份数状态。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！