【动态规划】HRBUST 1216 数的划分

题目链接：数的划分

Time Limit: 1000 MS Memory Limit: 65535 K

题目

Description
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。

Input
有多则测试数据。
对于每组测试数据，仅有一行，包括两个整数n，k (6<n<=200，2<=k<=6)。

Output
对于每组测试数据，输出一个整数，即不同的分法。

Sample Input
7 3

Sample Output
4

Hint
输入： 7 3
输出：4 {四种分法为：1，1，5; 1，2，4; 1，3，3; 2，2，3;}

Source
NOIp2001高中组

Recommend
黄李龙

思路

首先为了便于思考问题，我们把问题转换一下：有n个小棒，问有多少种划分方法，把这n个小棒放在k组当中。
假设当前小棒为i，需要划分为j组，每组至少一个小棒。
则首先给每组放上一个小棒，则还剩下i-j个小棒，这i-j个小棒可以都放在任意1组中，也可以分开放在2组中，3组中…j组中（j<=k）。
放在a组和放在b组（a!=b）的情况很明显是不同的情况（如5根小棒放在一起（6，1）和分成两堆（3，4））。

则，把i个小棒放到j组中的情况可以表示为：
dp[i][j] = dp[i-j][1] + dp[i-j][2] + … + dp[i-j][j-1] + dp[i-j][j] (*)

我们来花间一下这个式子，目标是让某些无穷的项用有限项代替。

不难发现：i-j = (i-1)-(j-1)

dp[i-1][j-1] = dp[(i-1)-(j-1)][1] + dp[(i-1)-(j-1)][2] + … +dp[(i-1)-(j-1)][j-1]

整理式子，将等式右边括号打开，得

dp[i-1][j-1] = dp[i-j][1] + dp[i-j][2] + dp[i-j][3] + … + dp[i-j][j-1] (**)

观察和（*）式和**(**)**式，发现两式只相差dp[i-j][j]这一项，即：

dp[i][j] = dp[i-j][j-1] + dp[i-j][j]

即为转移方程。

代码

注意剩余小棍分配的数量j既不能超过要求最大堆的数量k，也不能超过当前最大小棍个数i（即不存在3根小棍分到4堆的情况，这种情况就出现i-j为负数的情况）。

#include<bits/stdc++.h>
using namespace std;

int dp[300][300];
int n,k;

int main(void){
    ios::sync_with_stdio(false);
    while(cin>>n>>k){
        memset(dp,0,sizeof dp);
        dp[0][0] = 1;
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= i && j <= k ; j++)
                dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
        cout<<dp[n][k]<<endl;
    }
    return 0;
}