Serendipity

山有木兮木有枝

0%

划分数问题

发表于 更新于 分类于

划分数问题

有n个无区别的物品，将他们划分成不超过m组，求出划分方法数模M的余数。
输入:n,m,M = 4,3,10000
输出：4

特别的，当m=n时，叫做n的划分数。通俗的讲就是一个正整数n可以划分成多少个正整数的和？

我们可以这样定义：

dp[i][j] := 把j划分成个数不超过i的方案总数

为了不重复计算，我们把n的划分数归纳于一系列非负整数的集合ai,
$$
\sum_{i=1}^ma_i = n
$$
ai 的定义如上，列入4的3划分为{0,0,4},{0,1,3},{0,2,2},{1,1,2}，方案一{0,0,4}的a1,a2,a3分别是0,0,4，依次类推。

可以看出，每个集合里面有m个数，但是不都全为正整数。

所以我们可以将问题分成两类，一个是{ai}里面不包括0，一个是里面存在0。对于不存在0,将4的3划分数{1,1,2}作为例子，可以发现当里面的数个减去一，就变成了{0,0,1}，即1的3划分数，它们两个的个数是相同的。所以{ai-1}就对应了n-m的m划分就不难理解了，就是集合里的每个数减去一，一共减了m个。

dp[i][j] = dp[i][j-i]

对于存在0，就好比上面的{0,0,4},{0,1,3},{0,2,2},可以发现集合里面各去掉一个数就变成了{0,4},{1,3},{2,2}，即4的2划分。它们的个数是一样的。即

dp[i][j] = dp[i-1][j]

总结：

1
2
3
4
5
6
'''
由此可以发现 dp[3][4] = dp[3][1] + dp[2][4]
所以可以推出递推公式：
dp[i][j] = dp[i][j-i] + dp[i-1][j]
边界条件：dp[0][0] = 1
'''

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
有n个无区别的物品，将他们划分成不超过m组，求出划分方法数模M的余数
输入:
n,m,M = 4,3,10000
输出：
4
'''

n,m,M = 4,3,10000
dp = [[0 for i in range(n+1)] for j in range(m+1)]  #用mxn列表记录j的i划分
def DP():
    dp[0][0] = 1
    for i in range(1,m+1):
        for j in range(0,n+1):
            if j-i >= 0:    
                dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % M
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[m][n])
DP()

同样的问题：n的划分数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
'''
一个正整数可以划分为多个正整数的和，比如n=3时：
3；1＋2；1＋1＋1；
共有三种划分方法。
给出一个正整数，问有多少种划分方法。
数据规模和约定
n< =100
样例输入
3
样例输出
3
'''

n = int(input())
dp = [[0 for i in range(n+1)] for j in range(n+1)]
def DP():
    dp[0][0] = 1
    for i in range(1,n+1):
        for j in range(0,n+1):
            if j - i >= 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-i]
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n][n])
DP()

思维图：