数的划分
分析
f[i][j]记录把i个物品分为非空的j份的方案数。
f[i][j] = f[i - 1][j - 1] + f[i - j][j]。
分类讨论：是否存在一份物品的数量为1。
- 存在，接下来把
i - 1个物品分为j - 1份； - 不存在，为了保证这一点，提前拿出
j个物品放入每一份，接下来把i - j个物品分为j份。
如果每份可以为空，那么讨论是否存在一份物品的数量为0。
实现
#include <iostream>
using namespace std;
const int N = 210;
int n, k;
int f[N][N];
int main () {
cin >> n >> k;
f[0][0] = 1;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= i; ++ j)
f[i][j] = f[i - 1][j - 1] + f[i - j][j];
cout << f[n][k] << endl;
return 0;
}