20241018每日一题洛谷P2386
普及 每日一题 信息学竞赛 1206：放苹果
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
第一行是测试数据的数目t（0<=t<=20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
对输入的每组数据M和N，用一行输出相应的K。
看到题目第一眼，这不是排列组合吗？！
遂进行C A组合，未能找到严格的通项公式，只能递推寻找答案
思路如下：
对于m个苹果，n个盘子
首先考虑特殊情况：（实际上可以不用考虑）
m = 0 时：即没有苹果可以瓜分，有 0 种分法
n = 0 时：即没有盘子可以放置，有 0 种分法
m < 0 时：不存在实际情况，有 0 种分法
if (m==0) return 0;
if (n==0) return 0;
考虑递归公式：
从n个盘子开始，对于分苹果的方法有两种：
不分给第n个盘子||分给所有的盘子
先解释第一种情况：
从第n个盘子开始，假如后面的所有盘子也都不给分苹果
这样的话将会导致最后没有办法安置苹果，则为 n = 0 时的特殊情况 返回0
解释第二种情况：
从m个苹果开始，每次都给所有的盘子都分一个苹果，假如后面都是这样操作
则必会有一次操作后使得 m <= 0 这时显然返回 0
if (m<=0) return 0;
当 m = 1 时：这时如果盘子不为 0 个，则有且仅有一种分法，返回 1
当 n = 1 时：这时如果苹果不为 0 个，则有且仅有一种分法，返回 1
if (m==1) return 1;
if (n==1) return 1;
可以发现，在 m或n 等于 1 时递推已经有了返回值，则无需考虑 m或n 等于 0 时的情况
回过头我们来解释一下为什么会有这两种分苹果的方法
第一种方法不难想到，第二种方法可能有点困难
我们由下往上来考虑这个问题：
假设我们有一颗二叉树描述递归的过程
root节点为 (m,n) ，令左孩执行的操作为 (m,n) -> (m,n-1) ，右孩执行的操作为 (m,n) -> (m-n,n)
对整棵树的节点而言 ：
所有左孩执行的操作的方向为一条形似于由左下贯穿右上的直线
所有右孩执行的操作的方向为一条形似于由右下贯穿左上的直线
当 n = 1 的时候，即我们只有一个盘子可以放我们剩下的苹果
递归执行右孩操作可以得到一条形似于由右下贯穿左上的直线，这条直线位于所有由右孩操作组成的直线集的底层
当 n = 2 的时候，即我们只有两个盘子可以放我们剩下的苹果
递归执行右孩操作也可以得到一条形似于由右下贯穿左上的直线，这条直线位于 n = 1 的直线的上一层
同理，可以得出 n =n 的时候，这条右孩操作直线为直线集的顶层，从最后一层的特殊性，往回推出第一层该如何操作
即root节点的右孩操作该如何执行
核心代码如下：
using namespace std;
int count(int m, int n) {
if (m < 0) return 0;
if (m == 1) return 1;
if (n == 1) return 1;
return count(m-n, n) + count(m, n - 1);
}
int main()
{
int t;
scanf("%d", &t);
for (int i = 0; i < t; i++) {
int m, n,ans=0;
scanf("%d %d", &m, &n);
printf("%d", count(m, n));
}
return 0;
}