Description

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

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

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

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

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

1
2
3
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;
}