一、题目
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 }
四、相关知识点