[数据结构与算法][动态规划]数的划分

【数的划分】
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。

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

1，1，5； 1，5，1； 5，1，1；

问有多少种不同的分法。 输出一个整数，即不同的分法。

【输入】
两个整数n，k(6<n≤200，2≤k≤6)，中间用单个空格隔开。

【输出】
一个整数，即不同的分法。

【输入样例】
7 3

【输出样例】
4

思路：
dp[i][j] 指在有 i 个数划分为 j 个时所有的方法数
如果是最普通的方程的话应该长这样：
dp[i][j] = dp[i - j][1] + dp[i - j][2] + … + dp[i - j][j]
先把 i 个数在 j 份上每个都放上1，然后剩下了（i - j） 个
这（i - j）个可以分成一份或两份或三份或四份或者很多很多份，于是就有了这个动态转移方程。
可惜这个方程并不能写下来，而且过于繁琐

那么就再写一个：
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 - j][1] + dp[i - j][2] + … + dp[i - j][j - 1]

所以动态转移方程可以简化为：
dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];

代码如下：

#include <bits/stdc++.h>
using namespace std;
int dp[205][7];
int main(){
	int n,k;
	cin >> n >> k;
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			if (i >= j)
				dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
	cout << dp[n][k];
	return 0;
} 

(鸣谢elma_tww的思路解释，因为做完题目后太难解释，思路不好理解，所以参考了解释方法，很清晰！Thanks?(･ω･)ﾉ）
End