Python 动态规划：巧妙解决“放苹果”问题及其代码实现184

在算法的世界里，有这样一类问题，它们表面上看起来像简单的计数或组合，但深入探究，却能引出强大而优雅的解决方案——动态规划（Dynamic Programming, DP）。“放苹果”问题便是其中一个经典的代表。它不仅是面试中常考的题目，更是理解DP思想，特别是整数划分（Integer Partitioning）概念的绝佳切入点。作为一名专业的程序员，熟练掌握这类问题的解法，能够帮助我们更好地解决现实世界中资源分配、组合优化等复杂难题。

本文将深入探讨“放苹果”问题，从其数学本质、递归关系推导到两种主要的Python实现方式：带备忘录的递归（Top-Down DP）和迭代的动态规划（Bottom-Up DP）。通过详尽的代码示例、复杂度分析以及实际应用场景的讨论，力求为读者呈现一篇全面而优质的指南。

一、问题描述：什么是“放苹果”？

“放苹果”问题通常可以这样描述：

假设有 `m` 个完全相同的苹果，和 `n` 个完全相同的盘子。请问，有多少种不同的方法可以将这些苹果放入盘子中？允许有些盘子是空的，但盘子的顺序不作区分。

关键点：

苹果相同： 比如3个苹果A, B, C，分到盘子里是同一个结果。
盘子相同： 比如盘子1放2个，盘子2放1个，与盘子1放1个，盘子2放2个是同一种方法。
允许空盘： 有些盘子可以不放苹果。

举例说明：

`m = 7` 个苹果，`n = 3` 个盘子。

可能的分配方式有：

7 = 7

7 = 6 + 1

7 = 5 + 2

7 = 5 + 1 + 1

7 = 4 + 3

7 = 4 + 2 + 1

7 = 3 + 3 + 1

7 = 3 + 2 + 2

（注意：`6+1` 和 `1+6` 视为同一种，因为盘子相同。同时，`7` 本身也算一种，即一个盘子放7个，其余盘子为空。）
`m = 1` 个苹果，`n = 3` 个盘子。

只有一种方法：`1` (一个盘子放1个，其余空)。
`m = 0` 个苹果，`n = 3` 个盘子。

只有一种方法：`0` (所有盘子都为空)。

这个问题的本质就是整数划分问题的一个变种：将一个整数 `m` 划分成最多 `n` 个（非负）整数之和，且不考虑顺序。

二、递归关系与动态规划思想

解决这类问题的关键在于找到其递归关系。我们定义一个函数 `dp[m][n]`，表示将 `m` 个苹果放入 `n` 个盘子中的方法数。

1. 边界条件（Base Cases）：

`dp[0][n] = 1`： 当有0个苹果时，无论有多少个盘子，都只有一种方法（所有盘子都空着）。
`dp[m][0] = 0`： 当有非0个苹果，但盘子数为0时，无法放置，所以方法数为0。
`dp[m][1] = 1`： 当只有1个盘子时，无论有多少苹果，都只有一种方法（把所有苹果都放到这一个盘子里）。

2. 递归关系（Recurrence Relation）：

考虑 `m` 个苹果和 `n` 个盘子的情况 `dp[m][n]`。我们可以将其分为两种情况讨论：

情况 A：盘子的数量大于苹果的数量 (`n > m`)

如果盘子的数量 `n` 超过了苹果的数量 `m`，那么至少有 `n - m` 个盘子是空的。由于盘子是相同的，这些多余的空盘子并不会增加新的分配方式。因此，将 `m` 个苹果放入 `n` 个盘子中的方法数，等同于将 `m` 个苹果放入 `m` 个盘子中的方法数。

即：`dp[m][n] = dp[m][m]` (当 `n > m` 时)

情况 B：盘子的数量小于或等于苹果的数量 (`n m` 时)
`dp[m][n] = dp[m][n-1] + dp[m-n][n]` (当 `n int:
"""
计算将m个苹果放入n个盘子中的方法数（带备忘录的递归）。

Args:
m (int): 苹果的数量。
n (int): 盘子的数量。

Returns:
int: 放置方法总数。
"""
# 边界条件
if m < 0 or n < 0:
return 0 # 非法输入
if m == 0:
return 1 # 0个苹果，1种方法 (所有盘子为空)
if n == 0:
return 0 # 有苹果但没有盘子，0种方法
if n == 1:
return 1 # 只有1个盘子，1种方法 (所有苹果都放进去)

# 递归关系
if n > m:
# 盘子比苹果多，多余的盘子为空，等同于盘子数量和苹果数量一样多
return count_apple_ways_memo(m, m)
else: # n <= m
# 两种情况之和：
# 1. 至少有一个盘子是空的：相当于m个苹果放入n-1个盘子
# 2. 所有n个盘子都非空：每个盘子先放一个，剩余m-n个苹果放入n个盘子
return count_apple_ways_memo(m, n - 1) + count_apple_ways_memo(m - n, n)
# 示例测试
print("--- 带备忘录的递归 ---")
print(f"7个苹果，3个盘子：{count_apple_ways_memo(7, 3)} 种方法") # 预期输出: 8
print(f"1个苹果，1个盘子：{count_apple_ways_memo(1, 1)} 种方法") # 预期输出: 1
print(f"0个苹果，5个盘子：{count_apple_ways_memo(0, 5)} 种方法") # 预期输出: 1
print(f"5个苹果，0个盘子：{count_apple_ways_memo(5, 0)} 种方法") # 预期输出: 0
print(f"5个苹果，5个盘子：{count_apple_ways_memo(5, 5)} 种方法") # 预期输出: 7
print(f"5个苹果，7个盘子：{count_apple_ways_memo(5, 7)} 种方法") # 预期输出: 7 (等同于 5个苹果，5个盘子)

代码解释：

`@functools.lru_cache(None)`：这是Python标准库提供的一个装饰器，它会自动缓存函数的调用结果。当函数以相同的参数再次被调用时，会直接返回缓存的结果，而不会重新执行函数体。`None`表示没有大小限制。
函数内部首先处理各种边界条件，确保递归能够正确终止。
然后，根据 `n` 和 `m` 的关系，应用之前推导出的递归关系。

四、Python 代码实现：迭代的动态规划（Bottom-Up DP）

迭代的动态规划（或称为表格法）是自底向上（Bottom-Up）的实现方式。它通过填充一个二维数组（或DP表）来存储子问题的解，从小规模问题逐步推导出大规模问题的解。这种方法通常更易于理解循环逻辑，并且避免了递归深度限制和函数调用栈的开销。def count_apple_ways_dp(m: int, n: int) -> int:
"""
计算将m个苹果放入n个盘子中的方法数（迭代的动态规划）。

Args:
m (int): 苹果的数量。
n (int): 盘子的数量。

Returns:
int: 放置方法总数。
"""
if m < 0 or n < 0:
return 0 # 非法输入

# dp[i][j] 表示将i个苹果放入j个盘子中的方法数
# 初始化一个 (m+1) x (n+1) 的二维数组，并全部初始化为0
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 填充dp表的边界条件
# 当有0个苹果时，无论有多少个盘子，都只有1种方法 (所有盘子都为空)
for j in range(n + 1):
dp[0][j] = 1

# 当只有1个盘子时 (dp[i][1])，无论有多少苹果，都只有1种方法
# (注意：dp[0][1] 已经通过 dp[0][j] = 1 初始化了，这里可以省略，
# 或者从 i=1 开始填充，因为 dp[0][1] = 1 已经满足了)
for i in range(1, m + 1):
dp[i][1] = 1
# 迭代填充dp表
# i 代表苹果数 (从1到m)
# j 代表盘子数 (从2到n，因为dp[i][0]和dp[i][1]已初始化)
for i in range(1, m + 1):
for j in range(2, n + 1):
if j > i:
# 盘子比苹果多，多余的盘子为空，等同于盘子数量和苹果数量一样多
dp[i][j] = dp[i][i]
else: # j <= i
# 两种情况之和：
# 1. 至少有一个盘子是空的：dp[i][j-1]
# 2. 所有j个盘子都非空：dp[i-j][j]
dp[i][j] = dp[i][j - 1] + dp[i - j][j]

return dp[m][n]
# 示例测试
print("--- 迭代的动态规划 ---")
print(f"7个苹果，3个盘子：{count_apple_ways_dp(7, 3)} 种方法") # 预期输出: 8
print(f"1个苹果，1个盘子：{count_apple_ways_dp(1, 1)} 种方法") # 预期输出: 1
print(f"0个苹果，5个盘子：{count_apple_ways_dp(0, 5)} 种方法") # 预期输出: 1
print(f"5个苹果，0个盘子：{count_apple_ways_dp(5, 0)} 种方法") # 预期输出: 0
print(f"5个苹果，5个盘子：{count_apple_ways_dp(5, 5)} 种方法") # 预期输出: 7
print(f"5个苹果，7个盘子：{count_apple_ways_dp(5, 7)} 种方法") # 预期输出: 7 (等同于 5个苹果，5个盘子)
print(f"10个苹果，4个盘子：{count_apple_ways_dp(10, 4)} 种方法") # 预期输出: 41

代码解释：

`dp = [[0] * (n + 1) for _ in range(m + 1)]`：创建一个 `(m+1) x (n+1)` 大小的二维列表 `dp`。`dp[i][j]` 将存储 `i` 个苹果放入 `j` 个盘子的方法数。
初始化：

`dp[0][j] = 1`：0个苹果放入任意数量盘子，都只有1种方法（所有盘子空）。
`dp[i][1] = 1`：任意数量苹果放入1个盘子，都只有1种方法。


嵌套循环： 外层循环 `i` 遍历苹果数量从1到 `m`，内层循环 `j` 遍历盘子数量从2到 `n`。
填充逻辑： 根据前面推导的递归关系 `dp[i][j] = dp[i][i]` (当 `j > i` 时) 或 `dp[i][j] = dp[i][j-1] + dp[i-j][j]` (当 `j

2025-11-04

---

上一篇：Python时间与随机函数：日期、时间、随机数生成全解析

下一篇：Python函数的高级玩法：变量赋值、列表存储与动态执行深度解析