m划分问题
给出n个物品(完全一致,无法区分),要求分成m组,每一组可空,求划分数(组之间不考虑顺序)
dp[i][j]表示j的i划分数
那么我们可以将j的i划分,分为两种类型
- 每一组都不空
- 存在某一组或多组空 显然这两个加起来就是 j 的 i 划分的总数,且这两个没有交集,是最优子结构
每一组都不空
我们先考虑每一组都不空的情况(显然有j>=i).既然每一组都不空,我们索性从每个组中抽出一个物品,则抽取完后,也就是j-i个元素,分到i个组中,每个组都可空.也就是dp[i][j-i]
至少有一种空
我们在考虑至少有一组空的情况.既然至少有一组空,我们就拿走一个空的组,那么还是j个物品,然后分到i-1个组中,每一组可空.也就是dp[i-1][j]
总结
这样我们就得到了转移公式dp[i][j]=dp[i][j-1]+dp[i-1][j]
另外我们再讨论一些边界情况
- 首先,
在x=1或0时 dp[n][x]恒为1,也就是无论n是多少,也就是只有一个元素(或没有元素)时,也只有一种划分方法,这个是(1)的终点 - 其次,
在x=1或0时 dp[x][n] 恒为 1,也就是无论n是多少,只要划分成一组,就只有一种划分方法. (2)中的终点就是分组为1
AC代码
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
26
27
28
29
30
31
32
33
34
35
36
37
// POJ-1664
// 这个题比较奇葩,是m的n划分,为了和题意一样,导致后面有点绕,但是递推公式是对的
#include <iostream>
using namespace std;
int dp[15][15];
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> m >> n;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
dp[i][j] = 0;
}
}
for (int i = 0; i <= n; ++i) {
dp[i][0] = 1;
dp[i][1] = 1;
}
for (int j = 0; j <= m; ++j) {
dp[0][j] = 1;
dp[1][j] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j >= i) {
dp[i][j] = dp[i - 1][j] + dp[i][j - i];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[n][m] << endl;
}
return 0;
}
