数的划分

 1 //设f(n,k)为整数n拆分成k个数字的方案数，则可以分以下两种情况讨论。
 2 //(1)拆分的结果不包含1的情况：如果不包含1，我们把n拆分成k块时可以看做先将每一块加上个1，则n还剩余n-k，即f(n-k,k)
 3 //(2)拆分的结果包含1的情况：那么就直接选一个1，即f(n-1,k-1)。
 4 //
 5 //那么总递推式为 f(n,k)=f(n-k,k)+f(n-1,k-1)
 6 
 7 #include <iostream>
 8 #include <cstdio>
 9 #include <string>
10 #include <cstring>
11 #include <string>
12 #include <cmath>
13 #include <cstdlib>
14 #include <algorithm>
15 using namespace std;
16 typedef long long ll;
17 const int maxn = 205;
18 const int inf=0x3f3f3f3f;
19 const ll mod=1e9+7;
20 
21 int n,k,d[206][10];///d[i][j]把i个划分为j块
22 int main()
23 {
24     scanf("%d%d",&n,&k);
25     d[0][0]=1;
26     for(int i=1; i<=n; i++){
27         for(int j=1;j<=i&&j<=k; j++){
28             d[i][j]=d[i-1][j-1]+d[i-j][j];
29         }
30     }
31     printf("%d\n",d[n][k]);
32     return 0;
33 }