【题目描述】

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

【输入】

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

【输出】

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

【输入样例】

1
7 3

【输出样例】

8

【题目分析】

• 比较经典的递归题目（排列组合）

• 加上限制条件，一共可以催生出8种不同的题目（例如，盘子允许空或者不空就是两种情况）

• 先分析样例，然后总结规律，最后用公式代替（递归的主要思路）

• 也可以用递推规律去分析

• 所有苹果都必须放完
  

【从样例分析递推规律】

按照题目样例，7（M）个苹果放到3（N）个盘子中。可能存在下面几种情况。

第一类：

7   0   0
6   1   0
5   2   0
4   3   0

第二类：

5   1   1
4   2   1
3   3   1
3   2   1

可以看出一共有8种，可以分成两类。

下面我们开始列举其他数据分类讨论寻找规律。

第一类：M<N时：

• 假设1（M）个苹果放到2（N）个盘子中。只有1（M）种放法，而且至少空1（N-M）个盘子

• 假设1  (M)  个苹果放到3 （N）个盘子中。只有1（M）种放法，而且至少空2（N-M）个盘子

• 假设2（M）个苹果放到3（N）个盘子中。 只有2（M）种放法，而且至少空1（N-M）个盘子

• 假设2（M）个苹果放到4（N）个盘子中。 只有2（M）种放法，而且至少空2（N-M）个盘子......

可以看出，当N>M时，放法只有M种。N的大小不影响不同的放法种数。如果放到递归中，也就是f(m,n)=f(m,m)

第二类：M>=N时：

从样例数据可以看出，M>=N时，可以继续分成两类，包含空盘子（0）和不包含空盘子的情况。那么，我们继续分析

• 假设2（M）个苹果放到1（N）个盘子中。只有1种放法，没有空盘子

• 假设3（M）个苹果放到1（N）个盘子中。只有1中放法，没有空盘子

• 假设3（M）个苹果放到2（N）个盘子中。有2种放法（按照有没有空盘子分）。（3，0）和（2，1）

• 假设4（M）个苹果放到2（N）个盘子中。有3种放法（按照有没有空盘子分）。（4，0）、（3，1）、（2，2）

• 假设4（M）个苹果放到3（N）个盘子中。如果有一个空盘子，就是4个苹果放到2（N-1）个盘子中，那么跟上面的f(4,2)是一种情况。如果每个盘子至少一个。那么就是先相当于“先把每个盘子中放一个，剩余M-N个苹果放到N个盘子中”（注，此时M-N一定小于N，也就是跟第一类情况吻合）。那么这种情况就是

  F(M,N)=F(M,N-1)+F(M-N,N)。

  继续举例验证公式：

• 假设5（M）个苹果放到3（N）个盘子中。F（5，3）一共有下面5种。

5 0 0
4 1 0
3 2 0

3 1 1
2 2 1

F(M,N-1)=F(5,2)=3种

5 0

4 1
2 3

  F(M-N,N)=F(2,3)=2种（第一类已经证明了）

所以，递归的结论是：

M<N时：F(M,N)=F(M,M)

M>=N时：F(M,N)=F(M,N-1)+F(M-N,N)

递归出口条件：

• 当n=1时，所有苹果都必须放在一个盘子里，所以返回1；

• 当m==0(没有苹果可放)时，定义为1种放法；

所以递归部分核心代码是：

int fun(int m, int n) {//m个苹果放在n个盘子中共有几种方法
    if(m==0 || n==1)
        return 1;
    if(n>m)
        return fun(m,m);
    else
        return fun(m,n-1)+fun(m-n,n);
}

【递推规律】

除了递归外，我们还可以尝试用递推去做，最好的办法就是“表格法”（打表法）

注：并建议编程题用这种做法，即时画出表格，规律也不好总结

【DFS】

#include<iostream>
using namespace std;
int t,n,k;
int f[11][11];
int sum;
 
void dfs(int step,int num,int tar)
{
	if(tar==1)
	{
		sum++; 
		return ;
	}
	for(int i=step;i<=num/tar;i++)
		dfs(i,num-i,tar-1);
}
 
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		sum=0;
		dfs(0,n,k);//因为可以有空盘,所以从0开始 
		cout<<sum<<endl;
	}
	return 0;
}