將整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。
例如：n=7，k=3，下面三種分法被認為是相同的。
1,1,5; 1,5,1; 5,1,1;
問有多少種不同的分法。
輸入n，k (6<n<=200，2<=k<=6)
一個整數(shù)，即不同的分法。
這題閆令琪的一次測試中出過，當時由于把時間用在了前兩題比較復雜的題目上了，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;
}
另一種是動態(tài)規(guī)劃：
狀態(tài)轉移方程不太好發(fā)現(xiàn)f[i,j]=f[i-j,j]+f[i-1,j-1]
posted on 2010-01-06 18:37
lee1r 閱讀(252)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索