一、题目
0、题目链接
http://lx.lanqiao.cn/problem.page?gpid=T84（需要登录且需要 VIP 账户）
1、问题描述
将整数 n 分成 k 份，且每份不能为空，任意两份不能相同（不考虑顺序）。
例如：n = 7，k = 3，下面三种分法被认为是相同的。
1，1，5；1，5，1；5，1，1；
问有多少种不同的分法。
2、输入格式
两个正整数 n, k。
3、输出格式
一个正整数，即不同的分法。
4、样例输入
7 3
5、样例输出
4 // 四种分法为：1，1，5；1，2，4；1，3，3；2，2，3；
6、数据规模
6 < n <= 200，2 <= k <= 6
二、分析与思路
令 f[i][j] 表示 “数 i 被划分成 j 份的分法”，6 < i <= 200, 2 <= j <= 6，求解目标为 f[n][k]。
对于整数 i，如果需要划分为 j 份，首先每一份的值必然不为 0，故恒有 j <= i，即每份的最小值为 1，剩下的值为 i - j，而这个 i - j 我们可以全部放到 j 份中的任意一份，对应的是 f[i - j][1]（将数 i - j 划分成 1 份）也可以是其中 2, 3, ...（f[i - j][2, 3...]）份，这时候我们已经构建出了一个递推关系，也就可以开始求状态转移方程了。
依上述关系，可得：
f[i][j] = f[i - j][1] + f[i - j][2] + ... f[i - j][j] ①
又 f[i - 1][j - 1] = f[i - j][1] + f[i - j][2] + ... + f[i - j][j - 1] ②，将 ② 式代入 ① 式，可得：
f[i][j] = f[i - j][j] + f[i - 1][j - 1] ③，即状态转移方程。
尽管是道很简单的动态规划，但后面 ③ 式的简化我觉得没那么容易想到。如果直接使用 ① 式，时间复杂度为 O(n * k * k)，尽管这道题数据量小，是吃得消的，但一旦上调则难以通过。③ 式通过简单的数列知识对式子简化，时间复杂度也随之下降至 O(n * k)。
三、代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int n, k, f[205][7]; 5 6 int main() { 7 cin >> n >> k; 8 for (int i = 1; i <= n; i++) { 9 f[i][1] = 1; 10 for (int j = 2; j <= min(i, k); j++) 11 f[i][j] = f[i - j][j] + f[i - 1][j - 1]; 12 } 13 cout << f[n][k]; 14 return 0; 15 }
四、相关知识点