2001年 数的划分

数的划分

题目描述

将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种划分方案被认为是相同的。
1 1 5

1 5 1

5 1 1
问有多少种不同的分法。

输入描述

输入：n，k (6<n<=200，2<=k<=6)

 

输出描述 

输出：一个整数，即不同的分法。

样例输入 

 7 3

样例输出 

4

数据范围及提示

 {四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}

//动态转移方程：f[i][j]=f[i-j][j]+f[i-1][j-1];
//f[i][j]表示将i划分为j份的分法， 
//f[i-1][j-1]是第i个为1的情况；
//f[i-j][j]的每一种情况加一就是f[i][j]除了有1单独分的所有情况； 
#include<cstdio>
int f[202][7],n,k,ans;
int work(int n,int k)
{
    if(k==1||n==k) f[n][k]=1;    //将n分为1份或n份都只有一种分法； 
    else if(n>k) f[n][k]=work(n-k,k)+work(n-1,k-1);
    return f[n][k];
}
int main()
{
    scanf("%d%d",&n,&k);
    work(n,k);
    printf("%d",f[n][k]);
    return 0;
}