放苹果

放苹果_牛客题霸_牛客网

问题简述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

数据范围：0 <= m <= 10, 1 <= n <= 10

思路：动态规划

• 定义 dp(i, j) 表示 i 个苹果放到 j 个盘子中的分法数；则递推公式为

  dp(i, j) = dp(i, j - 1) + (i >= j ? dp(i - j, j) : 0)

• 记整个事件为 $Z$，事件 $A$ 表示“至少有一个盘子没有放苹果”，事件 $B$ 表示“每个盘子至少放了一个苹果”；问题的难点是想明白事件 $A$ 和 $B$ 为互斥事件，即 $B = \bar{A}$；

• 基于以上结论，简单推导：

  • 因为 $B = \bar{A}$，故 $Z=A \cup B$，记 $Z(i,j) = A(i,j) + B(i,j)$；

  • 当“至少有一个盘子没有放苹果”时，从中拿掉一个盘子方法数不变，即 $A(i,j) = Z(i,j-1)$；

  • 当“每个盘子至少放了一个苹果”时，从每个盘子中拿掉一个苹果方法数不变，即 $B(i,j) = Z(i-j,j)$；注意，此时需要 $i >= j$；

  • 综上，得递推公式 dp(i, j) = dp(i, j - 1) + (i >= j ? dp(i - j, j) : 0)；

• 递归基：当只有 1 个盘子或只有 1 个苹果时，只有一种放法；

Python 递归

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(i, j):
    if i == 1 or j == 1: 
        return 1
    return dp(i, j - 1) + (dp(i - j, j) if i >= j else 0)

row = input()
m, n = map(int, row.split())

print(dp(m, n))