將整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。
例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。
1,1,5; 1,5,1; 5,1,1;
問有多少種不同的分法。

輸入n，k (6<n<=200，2<=k<=6)

一個(gè)整數(shù)，即不同的分法。

這題閆令琪的一次測(cè)試中出過，當(dāng)時(shí)由于把時(shí)間用在了前兩題比較復(fù)雜的題目上了，4道題1個(gè)半小時(shí)，最后沒有時(shí)間做這題了……因?yàn)榍皟深}感覺可以拿下，不然不會(huì)用這么多時(shí)間。

很簡(jiǎn)單的一道題目。

兩種方法可以過，而且全部都是 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;
}

另一種是動(dòng)態(tài)規(guī)劃：

狀態(tài)轉(zhuǎn)移方程不太好發(fā)現(xiàn)f[i,j]=f[i-j,j]+f[i-1,j-1]