数据结构和算法：给空盘分苹果

内卷之源：

https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf?tpId=37&&tqId=21284&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking

题目描述：

 * 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放（本题潜藏意思是盘子可以空，但苹果必须放完），问共有多少种不同的分法？（用K表示）

 * 5,1,1和1,5,1是同一种分法。———— 即苹果、盘子均没有编号，不讲顺序，分完即可

 * 数据范围：0<=m<=10，1<=n<=10。

测试用例：

 *   input：7 3

 * output：8

 * 本题含有多组样例输入

思路分析：

 * 分析：用事件来描述，允许有的盘子空着不放这个事件Z包含两个互斥事件

          事件A → 存在空盘，即至少有一个盘子空着 ———— 问题转化为将m个苹果放到至多(n-1)个盘子里

          事件B → 不存在空盘，即每个盘子至少有一个苹果 ———— 问题转化为将(m-n)个苹果放到n个盘子里

          Z = A ∪ B，交集为空

 *       采用递归

 * 没有苹果(m=0)，仅1种分法 ———— 全空

 * 一个苹果(m=1)，仅1种分法 ———— 仅1个盘子有

 * 多个苹果(m≥2)，至少1种分法

编程实现(C++)：

/*
 ************************************************************
 * @author    SLF
 * @version	  V1.0.0
 * @date      26-Jun-2021
 ************************************************************
 */

#include <iostream>

using namespace::std;

int recursivePut(int m, int n);

int main(void)
{
	int K = 0;
	int m = 0, n = 0;
	
	while(cin>>m>>n)
	{
		//cout << m << " " << n << endl;
		if((0 > m) || (10 < m) \
		|| (1 > n) || (10 < n))
		{
			//printf("input param error... m=%d, n=%d\n", m, n);
			return 0;
		}
		
		K = recursivePut(m, n);
		cout << K << endl;
	}
	
	return 0;
}

int recursivePut(int m, int n)
{
	if((0 > m) || (1 > n))
	{//不存在空盘时苹果早已分完 或 存在空盘时空盘数量早已递归到一个
		return 0;
	}

	if((0 == m) || (1 == m))
	{//没有苹果 或 仅1个苹果(5,1,1和1,5,1是同一种分法)
		return 1;
	}

	return (recursivePut(m, n-1) + recursivePut(m-n, n)); //左边是 存在空盘，右边是 不存在空盘
}
           

郑重提示：①解题思路非最优，覆盖条件可能不全，仅供练习参考。

                  ②若有更佳思路或疑问，可在评论区留言相互讨论，不亦乐乎。

                  ③本文不允许转载，若认可本文，可点赞收藏关注。