Description

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

自己想了半天，什么排列组合之类的，后来去搜题解，才知道是用递归……

动态规划：其实这根将一个整数m分成n个整数之和是类似的。

另外一种表述是，给定了任意数量的现金，我们能写出一个程序，计算出所有换零钱方式的和数吗？（见《计算机程序的构造和解释》 p26）

设f[m][n]为将m分成最多n份的方案数，且其中的方案不重复，即每个方案前一个份的值一定不会比后面的大。则有：

f(m,n) = f(m,n - 1) + f(m - n,n)
       = 1 // m== 0 || n == 1
       = 0 // m < 0

f(m,n - 1)相当于第一盘子中为0，只用将数分成n - 1份即可。因为0不会大于任何数，相当于f(m,n - 1)中的方案前面加一个为0的盘子，而且不违背f的定义。所以f(m,n - 1)一定是f(m,n)的方案的一部分，即含有0的方案数。

f(m - n,n)相当于在每个盘子中加一个数1。因为每个盘子中加一个数1不会影响f(m,n - 1)中的方案的可行性，也不会影响f的定义。所以f(m - n,n)一定是f(m,n)的方案的一部分，即不含有0的方案数。(先把每个都放一个苹果，这样问题就转化为：m-n个苹果放进n个盘子里，盘子允许空)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;

int dynamic(int m, int n)
{
	if (m < 0) return 0;
	if (m == 0 || n == 1) return 1;
	return dynamic(m, n - 1) + dynamic(m - n, n);
}

int main(int argc, char const *argv[])
{
	int m, n, num;
	cin >> num;
	while (num--) {
		cin >> m >> n;
		cout << dynamic(m, n) << endl;
	}

	return 0;
}