（資訊學奧賽一本通 1304 洛谷 1025）數的劃分#線性動态規劃#

題意：把n分成k份，有多少種不同的方法。

當n小的時候深搜是0k的。（6<=n<=200）

是以說要使用動态規劃

狀态轉移方程

ans[k][n]表示把n分成k份的方案數。 ans[0][0]=1;

ans[i][j]=ans[i-1][j-1]+ans[i][j-i];

=至少有一個盒子隻有一個小球+沒有一個盒子隻有一個小球

至少有一個盒子隻有一個小球：因為盒子相同，是以=份數-1，球數-1

沒有一個盒子隻有一個小球：把每個盒子都抽出一個小球，是以份數不變，球數-i

#include<cstdio>  

using namespace std;  

int ans[10][205];  

int main(){  

    int n,k;

    scanf("%d%d",&n,&k);  

    ans[0][0]=1;  

    for(int i=1;i<=k;i++)

        for(int j=i;j<=n;j++)

            ans[i][j]=ans[i-1][j-1]+ans[i][j-i];

    printf("%d",ans[k][n]);

}