动态规划3-用记忆化技术解决背包问题

type

Post

status

Published

date

Mar 2, 2026

slug

summary

如何理解对背包问题实现记忆化？

想象一个场景：

你被要求多次计算 “用前5件物品装容量10的背包的最大价值”。

普通递归会像个愣头青，每次接到指令都从头开始重新推导，大量重复计算。

而记忆化递归会先准备一个 “笔记本”（表格 F），每次计算前先翻翻笔记本：

如果本子上有答案，直接抄答案。

如果本子上没有答案，再动手算，算完后立即把答案记到本子上，以后再有人问同样的问题，就能秒答。

🌟

记忆化 = 聪明的递归（带笔记本的递归）

结合伪代码理解步骤

这段代码展示的 “记忆化” 技术，是让计算机像人一样 “做笔记” 来避免重复劳动的高效方法。我们结合背包问题来通俗理解：

笔记本初始化

图中说把表格 F[0..n, 0..W]的单元格都用 -1初始化（-1表示“还没算过”）。

基础情况直接写好：F[0, j]和 F[i, 0]都设为 0（没有物品或没有容量时，价值为0）。

计算任何子问题 MFKnapsack(i, j)时

先查笔记本：if F[i, j] < 0意思是“如果本子上没记录过这个答案”（1表示没算过）。

如果没记录过，才需要真正计算。计算过程是递归的：

如果当前物品 i的重量大于剩余容量 j，肯定不能拿，答案就是 MFKnapsack(i-1, j)。
否则，在 “不拿 i” 和 “拿 i” 两个选项中选价值更大的：

不拿 i：MFKnapsack(i-1, j)
拿 i：Values[i] + MFKnapsack(i-1, j - Weights[i])

算完后立刻记到本子上：F[i, j] ← value

返回答案：return F[i, j]

以后再遇到相同的 (i, j)问题时

一查笔记本 F[i, j]不是 1，直接 return F[i, j]，省掉所有重复递归。

记忆化 vs. 普通递归 vs. 表格法（动态规划）

我们用爬楼梯的例子类比：

普通递归：算 f(10)时，会重复算 f(9)、f(8)...，而且算 f(9)时又会重复算 f(8)、f(7)... 指数级爆炸。

记忆化递归：算 f(10)时，第一次遇到 f(8)就把它算出来记下，下次再需要 f(8)直接查表。

表格法（自底向上动态规划）：直接从 f(1)、f(2)算到 f(10)，顺序填表，没有递归调用开销,但在求解给定问题时，有些较小的问题的解常常不是必须的。

记忆化的核心优势：

它只计算那些真正会被用到的子问题，而不是像表格法那样可能计算所有子问题。它是一种 “按需计算 + 缓存” 的策略，既有递归的直观性，又避免了重复计算。

举个例子

假设物品和之前一样：

物品	重量	价值
A	1	15
B	3	20
C	4	30

背包容量 W=4。

初始化表格：

(物品\|背包重量)	0	1	2	3	4
0	0	0	0	0	0
1	-1	-1	-1	-1	-1
2	-1	-1	-1	-1	-1
3	-1	—1	-1	-1	-1

计算 `MFKnapsack(3, 4)`的详细步骤

以下逐步展示自顶向下的递归计算与备忘录（F表）的填充过程。

步骤1：计算 MFKnapsack(3, 4)

查表 F[3][4]为 1，需计算。

物品3重量 4 ≤ 4，有两种选择：

不拿物品3：v1 = MFKnapsack(2, 4)

拿物品3：v2 = 30 + MFKnapsack(2, 0)

需先计算 MFKnapsack(2, 4)和 MFKnapsack(2, 0)。

步骤2：计算 MFKnapsack(2, 4)

查表 F[2][4]为 1，需计算。

物品2重量 3 ≤ 4，有两种选择：

不拿物品2：v1 = MFKnapsack(1, 4)

拿物品2：v2 = 20 + MFKnapsack(1, 1)

需先计算 MFKnapsack(1, 4)和 MFKnapsack(1, 1)。

步骤3：计算 MFKnapsack(1, 4)

查表 F[1][4]为 1，需计算。

物品1重量 1 ≤ 4，有两种选择：

不拿物品1：v1 = MFKnapsack(0, 4) = 0

拿物品1：v2 = 15 + MFKnapsack(0, 3) = 15 + 0 = 15

取最大值：max(0, 15) = 15

更新 F[1][4] = 15，返回 15。

步骤4：计算 MFKnapsack(1, 1)

查表 F[1][1]为 1，需计算。

物品1重量 1 ≤ 1，有两种选择：

不拿物品1：v1 = MFKnapsack(0, 1) = 0

拿物品1：v2 = 15 + MFKnapsack(0, 0) = 15 + 0 = 15

取最大值：max(0, 15) = 15

更新 F[1][1] = 15，返回 15。

步骤5：回到 MFKnapsack(2, 4)

现在有：

v1 = MFKnapsack(1, 4) = 15
v2 = 20 + MFKnapsack(1, 1) = 20 + 15 = 35

取最大值：max(15, 35) = 35

更新 F[2][4] = 35，返回 35。

步骤6：计算 MFKnapsack(2, 0)

查表 F[2][0]为 1，需计算。

物品2重量 3 > 0，因此只能不拿：

v = MFKnapsack(1, 0)

需先计算 MFKnapsack(1, 0)。

步骤7：计算 MFKnapsack(1, 0)

查表 F[1][0]为 1，需计算。

物品1重量 1 > 0，因此只能不拿：

v = MFKnapsack(0, 0) = 0

更新 F[1][0] = 0，返回 0。

步骤8：回到 MFKnapsack(2, 0)

v = MFKnapsack(1, 0) = 0

更新 F[2][0] = 0，返回 0。

步骤9：回到 MFKnapsack(3, 4)

现在有：

v1 = MFKnapsack(2, 4) = 35
v2 = 30 + MFKnapsack(2, 0) = 30 + 0 = 30

取最大值：max(35, 30) = 35

更新 F[3][4] = 35，返回 35。

备忘录（DP表）填充结果

下表展示了计算过程中被填充的单元格（行表示物品索引 i，列表示容量 j）：

i\j	0	1	2	3	4
0	0	0	0	0	0
1	0	15	ㅤ	ㅤ	15
2	0	ㅤ	ㅤ	ㅤ	35
3	ㅤ	ㅤ	ㅤ	ㅤ	35

注：F[0][*]和 F[*][0]默认初始为0，未列出的单元格在本次计算中未用到。

最终结果与最优解

最大价值：35

对应方案：选择物品1（重量1，价值15）和物品2（重量3，价值20），总重量恰好为4，总价值35。

这样，通过记忆化递归，我们避免了重复计算，并得到了正确结果。

最终，当你再次需要 MFKnapsack(2,4)时（比如在其他递归路径中），直接返回 F[2,4]=35，不必重新递归。

🌟

一句话总结记忆化

“计算前先查表，没算过才递归，算完立刻存表”

使用自顶向下的方式对给定问题求解，但同时维护一个类似自底向上动态规划算法使用的表格，它让递归有了记忆力，用空间换时间，将指数级复杂度的暴力递归优化成了多项式时间复杂度（和表格法相同），同时保留了递归自上而下的自然思路。