作者:翟天保Steven 题目描述:把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。 数据范围:0<=m<=10,1<=n<=10。 本题含有多组样例输入。 输入描述:输入两个int整数 输出描述:输出结果,int型 示例:输入: 7 3 输出: 8 解题思路:本题用递归和动态规划做。m个苹果放在n个盘子里,允许空盘,用function函数递归获得结果;当m或n小于等于0时,返回0;当m或n等于1时,返回1;当m和n都大于1时,function(m,n)其实可以分为两种情况,一是留一个空盘,即function(m,n-1),二是全满盘,每个盘先放一个苹果,即function(m-n,n),则有function(m,n)=function(m,n-1)+function(m-n,n),进入递归过程;其中当m等于n时,function(m,n)=function(m,n-1)+function(m-n,n)+1,因为此时的function(m-n,n)是function(0,n),而m和n一致时满盘的情况只有一种,就是每个盘子都放一个。综上,解题完毕。 测试代码:
|
|