放苹果

总时间限制: 1000ms 内存限制: 65536kB

描述

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

输入

第一行是测试数据的数目 t（0 <= t <= 20）。以下每行均包含二个整数 M 和 N，以空格分开。1<=M，N<=10。

输出

对输入的每组数据 M 和 N，用一行输出相应的 K。

样例输入

1
2

1
7 3

样例输出

1

8

来源

lwx@POJ

思路

定义了一个递归函数。这个函数接受三个参数：m，start 和 n。它的目标是计算有多少种方式可以将 m 分解为 n 个非负整数的和，其中每个整数都不小于 start。

如果 n 和 m 都是 0，那么函数返回 1，因为只有一种方式可以将 0 分解为 0 个数的和，那就是不选择任何数。如果 n 是 0 但 m 不是 0，那么函数返回 0，因为没有办法将一个非零数分解为 0 个数的和。

如果 n 和 m 都不是 0，那么函数进入一个循环，从 start 遍历到 m 的所有整数 i。对于每个 i，函数调用自身，将 m-i，i 和 n-1 作为参数。这是因为，如果我们选择了 i，那么我们需要找出有多少种方式可以将 m-i 分解为 n-1 个非负整数的和，而这些整数都不小于 i。函数将每次递归调用的结果累加到 sum 中。

最后，函数返回 sum，即所有可能的分解方式的数量。

由上图可知，在每次的递归中，只要将 start 设为 i，就可以保证不会出现重复的情况。

Code

C++

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

#include <bits/stdc++.h>
using namespace std;

int fun(int m, int start, int n) {
	int sum = 0;
	if(n == 0 && m == 0) return 1;
	else if(n == 0 && m != 0) return 0;
	for(int i = start; i <= m; i++) sum += fun(m-i, i, n-1);	
	return sum;
}

int main() {
	int t, m, n;
	cin >> t;
	for(int i = 1; i <= t; i++) {
		cin >> m >> n;
		cout << fun(m, 0, n) << endl;
	}
}

测试用例

样例 1

输入

1
2

1
7 3

输出

1

8

样例 2

输入

1
2

1
2 2

输出

1

2