数的划分

数的划分

//设f(n,k)为整数n拆分成k个数字的方案数，则可以分以下两种情况讨论。
//(1)拆分的结果不包含1的情况：如果不包含1，我们把n拆分成k块时可以看做先将每一块加上个1，则n还剩余n-k，即f(n-k,k)
//(2)拆分的结果包含1的情况：那么就直接选一个1，即f(n-1,k-1)。
//
//那么总递推式为 f(n,k)=f(n-k,k)+f(n-1,k-1)

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 205;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;

int n,k,d[206][10];///d[i][j]把i个划分为j块
int main()
{
    scanf("%d%d",&n,&k);
    d[0][0]=1;
    for(int i=1; i<=n; i++){
        for(int j=1;j<=i&&j<=k; j++){
            d[i][j]=d[i-1][j-1]+d[i-j][j];
        }
    }
    printf("%d
",d[n][k]);
    return 0;
}