M个同样的苹果放N个同样的盘子，允许有盘子空着, 问有多少种放法？

苹果都是相同的,盘子都是相同的

 

分析

令f(m,n)表示m个苹果放到n个盘子里有多少种放法，下面分类讨论:

 

m>n时,按是否有空盘子 分2种情况：

 

a.假设至少一个盘子空着，相当于f(m,n)=f(m,n-1)

   就是说m<n时无论如何放都会有空盘,那最多有n-1个盘子放了苹果,如果有两个空盘,那么f(m,n-2)还是等于f(m,n-1)的

b.所有的盘子都有苹果，假设每个盘子可以先放一个，问题就变成：m-n个苹果放到n个盘子，即f(m,n)=f(m-n,n)

总的放法为二者之和， f(m,n)=f(m,n-1)+f(m-n,n)

3. 临界条件

n=1时，所有苹果都放在同一个盘子里 f(m,n)=1

m=0时，没有苹果 f(m,n)=1

function fun(m,n){
    if(m<=1||n==1)
        return 1;
    else if ( n == 0)
        return 0;
    else if(n>m)
        return fun(m,n-1);
    return fun(m-n,n) + fun(m,n-1);
}