将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
输入n，k (6<n<=200，2<=k<=6)
一个整数，即不同的分法。
这题闫令琪的一次测试中出过，当时由于把时间用在了前两题比较复杂的题目上了，4道题1个半小时，最后没有时间做这题了……因为前两题感觉可以拿下，不然不会用这么多时间。
很简单的一道题目。
两种方法可以过，而且全部都是 0 ms AC
一种是搜索：
#include<stdio.h>
long n,k;
double ans=0;
void dfs(long s,long nn,long kk)
{
if(kk<=1)
ans++;
else
{
long i;
for(i=s;i<=nn/kk;i++)
dfs(i,nn-i,kk-1);
}
}
int main()
{
scanf("%ld%ld",&n,&k);
dfs(1,n,k);
printf("%.0lf\n",ans);
return 0;
}
另一种是动态规划：
状态转移方程不太好发现f[i,j]=f[i-j,j]+f[i-1,j-1]
posted on 2010-01-06 18:37
lee1r 阅读(237)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索