题解 | #放苹果#

背景

递归的关键在于：本次状态和上次状态之间的差异

理解

将m个苹果放到n个盘子中，有多少种放法？即求f(m, n)。
这个问题关键在于不同数量的苹果和盘子之间的方法关系，即只需要考虑多出来的苹果怎么放。因为：

1. 如果m<n，由于多出来的盘子并不会影响放法种数，所以f(m, n) = f(m, m)。
2. 如果m≥n，则存在两种情况：
   1. 有空盘，就相当于本身少了空盘的放法，所以f(m, n) = f(m, n-1)。（该公式递推多次即是多个空盘的情况）
   2. 无空盘，就相当于每个盘都有一个苹果，因为关键在于多出来的盘怎么放，那么每个盘拿掉一个苹果也不影响放法种数，所以f(m, n) = f(m-n, n)。

总的放法种数等于两者的和，即f(m, n) = f(m, n-1) + f(m-n, n)，也就是盘在减少的情况+苹果在减少的情况。
那么，最终盘会减少到n == 1，苹果会减少到m == 0，此时都只有1种放法。这里也就是递归的出口。

import sys


def func(m, n):
    """
    苹果放到盘子上只有下面两种情况：
    1. 有一个盘子是空的，则(m,n)的放置问题，变成了(m,n-1)
    2. 没有盘子是空的，则考虑剩下的苹果怎么放，变成了(m-n,n)
    备注：有多个盘子是空的，其实就是多次的一个盘子是空的递推问题
    :param m: 苹果数量
    :param n: 盘子数量
    :return: 方法数量
    """
    if m == 0 or n == 1:
        return 1
    elif n > m:         # 由于每个盘拿掉一个苹果，所以可能存在空盘情况，也需要考虑进去
        return func(m, m)
    else:
        return func(m, n-1) + func(m-n, n)  # 两种情况的方法数量之和


for s in sys.stdin:
    m, n = map(int, s.split())      # 格式化输入的m和n
    if m < n:       # 存在空盘情况
        n = m
    print(func(m, n))