放苹果问题

放苹果

1. 问题描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

2. 解决思路

令f(m,n)表示m个苹果放到n个盘子有多少种分法，按照是否有空盘子分为2种情况：

• 假设至少有一个空盘子，则f(m,n)=f(m,n-1)
• 没有空盘子，则每个盘子上至少有一个苹果，则问题转化为将m-n个苹果放在n个盘子有多少种分法，即求f(m-n, n)

所以，f(m,n)=f(m, n-1) + f(m-n, n)

边界条件：

1. m=1时，只有一种分法，即有一个盘子为1个，其他为0个。f(m, n)=1
2. m=0时，每个盘子都是空盘。f(m, n)=1
3. n=1时，所有苹果放在一个盘子里。f(m,n)=1
4. n=0时，没有盘子。f(m,n)=0

3. 案例分析——放苹果

def func(m, n):
    if m <= 1 or n == 1:
        return 1
    elif n == 0:
        return 0
    else:
        return func(m, n-1) + func(m-n, n)

if __name__=='__main__':
    m, n = map(int, input().split())
    print(func(m, n))