将n个小球放到k个盒子中的情况总数 = (a)至少有一个盒子只有一个小球的情况数 + (b)没有一个盒子只有一个小球的情况数
这样写出表达式：
然后将上面的思路化为递归式：
设f(n, k)代表将n个小球放到k个盒子中且没有空盒的情况，那么f(n, k) = f(n-1, k-1) + f(n-k, k)
而当k=1时只有1种方法(小球全部放进1个盒子)
// luogu-judger-enable-o2
/*******************
* problem: P1025 数的划分.
* user ID: 63720.
* user name: 航空信奥.
* time: 2018-05-14.
* mode: C++.
* upload place: Luogu.
*******************/
#include <stdio.h>
#include <iostream>
#define ll long long
using namespace std;
ll f(int n, int k)
{
if (k <= 0 || n < k)
return 0; //* 有空盒或有球放不下去
if (n == k)
return 1; //* 一个盒子放一个球
else
return f(n-1, k-1) + f(n-k, k); //* 递归求解
}
int main() // 完美主程序
{
ll n, k;
cin >> n >> k;
cout<< f(n, k);
return 0;
}
不加O2，1132ms，差点挂。
递归转递推（优化，0ms）
// luogu-judger-enable-o2
/*******************
* problem: P1025 数的划分.
* user ID: 63720.
* user name: 航空信奥.
* time: 2018-05-14.
* mode: C.
* upload place: Luogu.
*******************/
#include <stdio.h>
const int MaxK = 6 + 1;
const int MaxN = 200 + 1;
/*******************
* 0ms优化 ：
* 采用动态规划的思想，将递归转化为二维数组模式
* 注意开数组时，最好把空间大小+1
*******************/
int main()
{
int n, k;
scanf("%d%d", &n, &k);
int ans[MaxK][MaxN] = {0};
ans[0][0] = 1;
//f(n, k) = f(n-1, k-1) + f(n-k, k)
for (int i = 1; i <= k; i++)
for (int j = i; j <= n; j++)
ans[i][j] = ans[i - 1][j - 1] + ans[i][j - i];
printf("%d", ans[k][n]);
}