题解 | 递归#放苹果#

递归思路：

• 需要返回的结果： f(m,n)（方法数量）
• 按照n,m 分为两种情况：
  • n>m:需要去掉n-m个盘子，故：f(m,n)=f(m,m)
  • n<=m: 考虑两种互斥事件（形成m,n可以每次递归递减的情况）：
    • 每个盘子至少放一个: f(m,n) = f(m-n,n)
    • 至少有一个盘子是空的: f(m,n) = f(m,n-1)
• 退出递归的条件(题目条件** 0<=m<=10, 1<=n<=10**)：
  • m 一直递减，直至苹果 m=0: 说明盘子已经全部完成放置，f(m,n)=1 (m=0可理解为0个苹果放到n个盘子里，只有一种方法，边界条件）
  • n 一直递减，直至苹果 n=1: 剩余苹果全部放在这个盘子里, f(m,n)=1

def f(m,n):
    if m ==0 or n==1:
        return 1
    elif n > m:
        return f(m,m)
    else:
        return f(m-n,n)+f(m,n-1)
while True:
    try:
        m,n = list(map(int,input().split()))
    except:
        break
    else:
        print(f(m,n))