M28906: 数的划分

dfs, dp, http://cs101.openjudge.cn/practice/28906/

将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,5;

1,5,1;

5,1,1.

问有多少种不同的分法。

输入

一行两个整数 n,k （6< n <= 200，2 <= k <= 6），用空格隔开。

输出

1 个整数，即不同的分法。

样例输入

sample1 input:
7 3

sample1 output:
4

样例输出

sample2 input:
7 2

sample2 output:
3

提示

dfs, dp 本题数据范围较小, dfs也能过, 如果要限制时间复杂度的话可以考虑增大数据范围。

来源

2024 TA-wjl. https://www.luogu.com.cn/problem/P1025

这个题实际上是 “将正整数 n 划分成 k 个正整数的无序划分数”，常称为 “整数划分（分成固定份数）问题”。

✅思路分析

方法 1：DFS（带上限限制）

思路：

按递增顺序生成划分（例如当前最小数 start）。
确保不重复计数（即下一份的最小值 ≥ 当前份的最小值）。
当分出 k 份时检查总和是否等于 n。

python

from functools import lru_cache

def count_partitions(n, k):
    @lru_cache(maxsize=None)
    def dfs(n, k, start):
        if k == 1:
            return 1 if n >= start else 0

        count = 0
        for i in range(start, n + 1):
            count += dfs(n - i, k - 1, i)
        return count
    return dfs(n, k, 1)

n, k = map(int, input().split())
print(count_partitions(n, k))

python

def dfs(n, k, start):
    """把 n 分成 k 份，每份 >= start"""
    if k == 1:  # 只剩最后一份
        return 1 if n >= start else 0
    count = 0
    # 关键剪枝：i 最大为 n // k
    for i in range(start, n // k + 1):  # 保证剩下的 k-1 份至少每份1
        count += dfs(n - i, k - 1, i)
    return count

n, k = map(int, input().split())
print(dfs(n, k, 1))

❓为什么上限是 n // k？

因为我们还要分出 k-1 份，且每份 至少为 i（因为非递减，后续每份 ≥ 当前 i）。
所以总共至少需要 i * k（当前份 i + 后面 k-1 份每份 ≥ i）。
为了保证 i * k ≤ n，必须有 i ≤ n // k。
这个剪枝非常重要，避免无效搜索（比如当前取太大，后面不够分）。

✅ 实际上，更严格的推导是：剩余 n - i 要分给 k-1 份，每份 ≥ i，所以需要 n - i ≥ (k - 1) * i → n ≥ k * i → i ≤ n // k。

加上 @lru_cache 是强烈推荐的优化

python

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n, k, start):
    if k == 1:
        return 1 if n >= start else 0
    count = 0
    for i in range(start, n // k + 1):
        count += dfs(n - i, k - 1, i)
    return count

n, k = map(int, input().split())
print(dfs(n, k, 1))

方法 2：DP 记忆化（效率更高）

我们定义 dp[n][k] 表示将 n 分成 k 份的不同分法数。递推式：

dp[n][k] = dp[n-1][k-1] + dp[n-k][k]

解释，将 i 分成 j 份的方案分为两类，至少有一个1，所有数都 ≥ 2：

第一种情况：至少有一份是 1，问题变成把 n-1 分成 k-1 份（抽出一份1）。
第二种情况：每份至少 1，于是我们可以先给每份减去 1，问题变成把 n-k 分成 k 份；

边界条件：

dp[i][1] = 1    # 只能分成1份
dp[i][i] = 1    # 每份都是1

代码：

python

n, k = map(int, input().split())

dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][1] = 1
    if i <= k:
        dp[i][i] = 1

for i in range(2, n + 1):
    for j in range(2, k + 1):
        if i > j:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]

print(dp[n][k])

总结

方法	思路	复杂度	适用范围
DFS + 剪枝	枚举每份最小值	指数级，但可过小范围	n ≤ 200, k ≤ 6 ✅
DP	利用划分递推式	O(n·k)	大范围更快

【靳熙恒 25物理学院】思路：定义一个函数，返回值是把n分成k份的总情况数，函数内使用j在n内移动，依次返回把n-j分成k-1份的总情况数，并加起来即可，递归到k=1则只有一种情况，返回1。这道题的关键在于如何避免重复，这里可以通过限制j的移动范围，来确保较小的部分总是出现在前面的。具体来说，j的移动上限是floor(n/k)，因为平均分的话每一份就是n/k，如果j超过这个范围，那后续必然会出现小于j的部分，而其相对应的情况应当在j之前的取值中就已经涉及了，所以不能再加，否则重复；同样，j还需要一个下限i，其取值是上一层递归进入本层时上一层j的取值，本轮j应当不小于这个值，不然得到的情况应该是在上一层递归j较小时就已经算过的，也会重复。正如题目所说，本题数据不大，所以不用dp，单纯的dfs也过了。考场AC。

python

import math

n,k=map(int,input().split())

def sum(n,k,i):
    ans=0
    if k==1:
        return 1
    area=math.floor(n/k)
    if area>=i:
        for j in range(i,area+1):
            ans+=sum(n-j,k-1,j)
    return ans

print(sum(n,k,1))

M28906: 数的划分 ​

M28906: 数的划分