动态规划——整数划分

题目描述  Description 将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5; 1，5，1; 5，1，1;

问有多少种不同的分法。 输入输出格式  Input/output 输入格式：

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

输出格式：

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

输入输出样例 Sample input/output

输入样例：

7 3

输出样例：

4

解题思路： 根据本题要求，要将整数n划分为k部分，而且在不考虑顺序的情况下每种划分互不相同。 在此可以把问题抽象为一下模型： 有n个箱子，要把它们垒成k栋，可以假设箱子按某种满足该要求的方式已经摆好，现在从最底层每栋拿掉一个箱子，这样就只有两种情况： 1）之前每栋箱子的数量都多于1，则拿掉箱子后总栋数不变，则之前排列n个箱子成k栋的情况数与之后排列n-k个箱子成k栋的情况数是一样的 2）之前有一栋箱子的数量是1，则之前排列n个箱子成k栋的情况数与之后排列n-1个箱子成k-1栋的情况数相同 于是得出递推方程dp[n][k]=dp[n-j][k]+dp[n-1][k-1]; 出口是：dp[i][1]=1;

源程序：

#include <stdio.h>

const int maxn=200;
const int maxk=6;
long dp[maxn+1][maxk+1];
int k,n;
int main()
{
    for(int i=1;i<=maxn;i++)
    dp[i][1]=1;
    for(int i=1;i<=maxn;i++)
    for(int j=2;j<=maxk;j++)
    if(i>=j)
    dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
    while(~scanf("%d%d",&n,&k))
    printf("%ld\n",dp[n][k]);
    return 0;
}