题目描述
题目描述
把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
数据范围：0<=m<=10，1<=n<=10。
本题含有多组样例输入。
输入描述:
输入两个int整数
输出描述:
输出结果，int型
示例1
输入
7 3
输出
8
题目链接：https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf?tpId=37&tqId=21284&rp=1&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking&tab=answerKey
思路：这题还是没有那么简单的，最容易想到的放苹果策略就是：m个苹果放在n个盘子里，每个苹果有n种可能性，然后我就瞎想，就想不出来。实际上要把这种策略抽象一下，不管怎么决策每一个苹果的方法，最后的结果总是有的有，有的空，那结合起来就是：
1.每个盘子放1个，然后继续处理，put(m-n,n)
2.有1个盘子不放，然后处理put(m,n-1)
仔细想想所有的情况都能被这种策略覆盖。比如7个苹果2个盘子，前3轮都是每个盘子放1个苹果，最后的时候只能选择1个盘子不放了，因为put(1-2,2) 中1-2=-1小于0,只能执行put(1,2-1)返回1。
分析一下递归结束条件：
如果苹果数 小于 0，那肯定放不成功，所以返回0。1个苹果2个盘子都放，咋可能呢，put(1-2,2)返回0。
如果 苹果数 ==1 或者 ==0 ，直接返回1。比如put(2-2,2),2个苹果2个盘子都各放1个，返回1没问题。put(3-2,2)，3个苹果2个盘子都各放1个还剩1个苹果，返回1没问题。
如果只有1个盘子，你有多少苹果也只有1种放置方法啊，返回1没问题。
#include <iostream>using namespace std;
int putApple(int m,int n)
{if(m<0)return 0;//比如put(1-2,2),1个苹果没法每个篮子都放一个嘛，那就是失败，返回0就行了if(m==0 || m==1){return 1;//如果剩0个苹果刚好结束嘛，是1种情况，比如put(2-2,2);还有一种put(3-2,2),只剩1个苹果了，那就能1种情况嘛}if(n==1){return 1;//只剩下1个篮子，只能是1种情况}return putApple(m-n,n)+putApple(m,n-1);
}int main(){int m, n;while(cin>>m>>n){cout<<putApple(m,n)<<endl;}return 0;
}
