题目分析

1. 题目给我们苹果的数量m和盘子的数量n
2. 要将苹果放在盘子里，可以允许空盘，问有多少种放置方案
3. 但是盘子顺序是可以任意调换的，调换前后认为是同一种放置方案

方法一：递归

• 实现思路
  • 我们递归的最终结果是要返回solution(m,n)
  • 递归退出条件：
    • 如果没有苹果，则说明放置已经完成，方案已定，只能为1
    • 如果有一个苹果，则放在剩下哪一个盘子中都是一样的，因此方案数也是1
    • 如果只有一个盘子，则手上的苹果必须全部放在这一个盘子中，因此方案数也是1
  • 如果盘子数量大于苹果数量
    • 则必定有n-m个盘子空着，所以必定的事件不会影响方案数
  • 如果盘子数量小于等于苹果数量

    • 则考虑是不是要放满所有的盘子

    • 如果要空一个盘子，则有solution(m,n-1)种方案

    • 如果不要空这些盘子，则相当于所有盘子里至少会放一个苹果，那就相当于每个盘子都拿掉一个苹果，放了也白放不影响方案数量，因此有solution(m-n,n)种方案

def solution(m, n):
    if m == 0 or m == 1 or n == 1:                  # 如果没有苹果了或只有1个苹果，则方案数返回1；如果只有一个盘子了，剩下的苹果必须全放盘子里，因此也只剩下一种方案
        return 1
    elif n > m:                                     # 如果盘子数量多于苹果，说明必定有n-m个盘子会空着，因此必定的事情不会影响方案数
        return solution(m, m)
    else:                                           # 如果苹果多，则要考虑盘子中是否要放苹果，如果空一个，则要递归(m,n-1)；如果不空，则相当于所有盘子都要放至少一个苹果，这个条件等价于所有盘子都少掉一个苹果的方案数
        return solution(m, n-1) + solution(m-n, n)
    return
    

while True:
    try:
        m, n = map(int, input().split())
        print(solution(m, n))
    except:
        break

复杂度分析

• 时间复杂度： $O(2^n)O(2^n\; )$，画出递归树，执行时间复杂度即为$2^{n}2^n$ （同斐波拉契数列）
• 空间复杂度：$O(n)O(n)$，递归栈的深度。

方法二：动态规划

• 实现思路
  • 我们将前面的递归思路进行迭代化得到动态规划的解法
  • 边缘节点处理
    • 如果没有苹果，则说明放置已经完成，方案已定，只能为1
    • 如果有一个苹果，则放在剩下哪一个盘子中都是一样的，因此方案数也是1
    • 如果只有一个盘子，则手上的苹果必须全部放在这一个盘子中，因此方案数也是1
  • 动态规划数组处理
  • 如果盘子数量大于苹果数量
    • 则必定有n-m个盘子空着，所以必定的事件不会影响方案数
  • 如果盘子数量小于等于苹果数量
    • 则考虑是不是要放满所有的盘子
    • 如果要空一个盘子，则有solution(m,n-1)种方案
    • 如果不要空这些盘子，则相当于所有盘子里至少会放一个苹果，那就相当于每个盘子都拿掉一个苹果，放了也白放不影响方案数量，因此有solution(m-n,n)种方案

• 定义动态规划数组dp[i][j]的含义为对于i个苹果和j个盘子有多少种放置方案
• 我们分成两种情况分析：
  • 当时，苹果数量比盘子数量少，则盘子一定会空，因此当前的方案数有转移方程$dp[i][j]=dp[i][i]dp[i][j]\; =\; dp[i][i]$
  • 当$i>ji\; >\; j$时，苹果数量多于盘子数量，则要考虑是否每个盘子都要装苹果，如果不装满所有的盘子，相当于盘子数量少一个，则因该取值$dp[i][j-1]dp[i][j-1]$，如果装满所有的盘子，则所有盘子里面至少有一个苹果，相当于所有盘子里面都去掉一个苹果再进行分配，此时应该取值$dp[i-j][j]dp[i-j][j]$，因此则有转移方程$dp[i][j]=dp[i-j][j]+dp[i][j-1]dp[i][j]\; =\; dp[i-j][j]\; +\; dp[i][j-1]$
• 综上转移方程为

def solution(m, n):
    dp = [[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(m+1):
        dp[i][1] = 1            # 如果只有一个盘子则只有一种放置方案
    for j in range(1, n+1):
        dp[0][j] = 1            # 如果没有苹果则只有一种放置方案
        dp[1][j] = 1            # 如果只有一个苹果也相当于只有一种方案
    for i in range(2, m+1):
        for j in range(2, n+1):
            if i < j:                                # 如果苹果数量少，则盘子一定会空，所以去除那些空的盘子其实不影响方案数
                dp[i][j] = dp[i][i]
            else:                                    # 如果苹果数量多，则考虑是否要装够j个盘子，如果不装够则有dp[i][j-1]，如果装够则相当于从所有盘子同时去掉一个苹果无影响，则有dp[i-j][j]
                dp[i][j] = dp[i-j][j] + dp[i][j-1]
    
    return dp[m][n]
    
while True:
    try:
        m, n = map(int, input().split())
        print(solution(m, n))
    except:
        break

复杂度分析

• 时间复杂度：$O(mn)O(mn)$，双重循环的时间开销
• 空间复杂度：$O(mn)O(mn)$，动态规划矩阵的空间开销