1304：数的划分

【算法分析】
? ? ? ?本题可以类比信息学奥赛一本通 1222 放苹果，上题是允许有空的盘子，本题数字拆分问题可以等价地描述为：将n个相同的苹果分在k个相同的盘子中，每个盘子至少有1个苹果的方案数。下面在放苹果的问题背景下描述思路。

1. 状态定义
状态定义：dp[i][j]：将i个相同的苹果分放在j个相同的盘子中的方案数。
初始状态：将i个相同的苹果放在1个相同的盘子中，有1种方案，即dp[i][1] = 1。
如果苹果数小于盘子数，那么一定有某个盘子中分不到苹果，这不符合每个盘子至少有1个苹果，因此只有0种方案。即当i < j时，dp[i][j] = 0。

2. 状态转移方程
考虑分放苹果后是否存在某盘子中只有1个苹果，来分割集合。

子集1：存在某盘子中只有1个苹果，那么该情况下的方案数等同于：将i-1个苹果放入其余j-1个盘子的方案数，为：dp[i-1][j-1]
子集2：不存在某盘子中只有1个苹果，也就是每个盘子的苹果数量大于等于2。这相当于先在每个盘子各放一个苹果，用掉了j个苹果。然后要做的事情相当于：将剩下的i-j个苹果放入j个盘子，每个盘子中放至少1个苹果。该情况的方案数为：dp[i-j][j]
以上两种情况得到的方案数加和，即为将i个相同的苹果分放在j个相同的盘子中的方案数。即dp[i][j] = dp[i-1][j-1] + dp[i-j][j]
?

【参考代码】

#include<bits/stdc++.h>
using namespace std;
int n, k, dp[205][10];//dp[i][j]:将数字i拆分为j个数字相加的方案数 
int main()
{
    cin >> n >> k;
    for(int i = 0; i <= n; ++i)
    	dp[i][1] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= k && j <= i; ++j)
            dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
    cout << dp[n][k];
    return 0;
}