动态规划（一）：一维与背包
第二十七章：动态规划（一）— 一维与背包
动态规划（Dynamic Programming，DP）是面试中考查频率最高的算法范式，没有之一。它的核心思想只有一句话：把一个大问题拆成重叠的子问题，只算一次每个子问题，把结果存起来复用。
如果你觉得 DP 难，多半是因为你在试图"想出状态转移方程"。实际上，DP 的正确学习路径是：先写暴力递归 → 发现重复计算 → 加记忆化 → 改写成自底向上的循环。走完这四步，DP 就不神秘了。
Level 1 · 你需要知道的
27.1 从暴力递归到动态规划
经典入门题：爬楼梯（LeetCode #70）
你在爬楼梯，每次可以爬 1 级或 2 级。n 级楼梯有几种不同的爬法？
第一步：暴力递归
def climb_stairs_brute(n):
if n <= 1:
return 1
return climb_stairs_brute(n - 1) + climb_stairs_brute(n - 2)
这和斐波那契数列完全一样。时间 O(2ⁿ)，n = 45 就要跑几秒。
第二步：发现重复计算
画递归树就能看到，climb(3) 被算了很多次：
climb(5)
/ \
climb(4) climb(3)
/ \ / \
climb(3) climb(2) climb(2) climb(1)
/ \
climb(2) climb(1)
第三步：加记忆化（Top-Down）
def climb_stairs_memo(n, memo={}):
if n <= 1:
return 1
if n in memo:
return memo[n]
memo[n] = climb_stairs_memo(n - 1) + climb_stairs_memo(n - 2)
return memo[n]
用一个字典存已经算过的结果。时间 O(n)，空间 O(n)。
第四步：自底向上（Bottom-Up）
def climb_stairs_dp(n):
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
第五步：空间优化
发现 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，不需要整个数组：
def climb_stairs_optimized(n):
if n <= 1:
return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
时间 O(n)，空间 O(1)。从 O(2ⁿ) 到 O(n)，这就是动态规划的威力。
27.2 DP 的三个核心要素
每个 DP 问题都需要定义三样东西：
| 要素 | 含义 | 爬楼梯示例 |
|---|---|---|
| 状态 | dp[i] 代表什么 | dp[i] = 爬到第 i 级的方法数 |
| 转移方程 | dp[i] 怎么从之前的状态算出来 | dp[i] = dp[i-1] + dp[i-2] |
| 初始条件 | 最小的子问题的答案 | dp[0] = 1, dp[1] = 1 |
状态定义是最难的部分。如果状态定义对了，转移方程通常自然就出来了。
27.3 一维 DP 经典题
打家劫舍（LeetCode #198）
沿着一条街有 n 间房子，每间有一定金额。你不能连续偷相邻的两间，问最大收益。
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# dp[i] = 偷到第 i 间房子的最大收益
# 选择：偷 i（跳过 i-1）或不偷 i（取 i-1 的结果）
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
# 空间优化
def rob_optimized(nums):
if not nums:
return 0
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
零钱兑换（LeetCode #322）
给定不同面额的硬币和一个总金额，求最少需要几枚硬币凑出总金额。
def coin_change(coins, amount):
# dp[i] = 凑出金额 i 需要的最少硬币数
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
return dp[amount] if dp[amount] != float('inf') else -1
状态：dp[i] = 凑出金额 i 的最少硬币数
转移：dp[i] = min(dp[i - coin] + 1) 对所有 coin
初始：dp[0] = 0
最长递增子序列（LeetCode #300）
def length_of_lis(nums):
if not nums:
return 0
n = len(nums)
# dp[i] = 以 nums[i] 结尾的最长递增子序列长度
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
时间 O(n²)。可以用二分查找优化到 O(n log n)，详见第 22 章。
27.4 判断一个问题能否用 DP 解决
DP 适用的两个条件：
-
最优子结构：问题的最优解包含子问题的最优解。换句话说，你可以通过子问题的最优解构造出原问题的最优解。
-
重叠子问题：不同的递归路径会反复计算相同的子问题。如果子问题不重叠（每个子问题只算一次），那就是分治而不是 DP。
反例：最长路径问题（无权图）。这个问题没有最优子结构，因为最长路径可能需要"绕路"，子路径不一定是子问题的最优解。这个问题实际上是 NP-hard 的。
27.5 记忆化 vs 自底向上
| 特性 | 记忆化（Top-Down） | 自底向上（Bottom-Up） |
|---|---|---|
| 实现方式 | 递归 + 缓存 | 循环 + 数组 |
| 是否计算所有子问题 | 否（只算需要的） | 是（全部计算） |
| 栈溢出风险 | 有（递归深度） | 无 |
| 空间优化 | 较难 | 容易（滚动数组） |
| 调试 | 递归栈难跟踪 | 打印数组即可 |
| 面试推荐 | 快速写出正确解 | 优化时间/空间时 |
面试策略：先用记忆化写出正确解（快且不易出错），如果面试官要求优化，再改写为自底向上 + 空间优化。
Level 2 · 它是怎么运行的
27.6 0-1 背包问题
经典问题：有 n 个物品，每个物品有重量 w[i] 和价值 v[i]。你有一个承重为 W 的背包，每个物品只能选一次。求能装下的最大总价值。
def knapsack_01(weights, values, W):
n = len(weights)
# dp[i][j] = 考虑前 i 个物品，背包容量为 j 时的最大价值
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i-1], values[i-1]
for j in range(W + 1):
dp[i][j] = dp[i-1][j] # 不选第 i 个物品
if j >= w:
dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v) # 选第 i 个
return dp[n][W]
状态：dp[i][j] = 考虑前 i 个物品、容量为 j 时的最大价值
转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
初始：dp[0][j] = 0（没有物品可选）
空间优化到一维：
注意转移方程中 dp[i][j] 只依赖 dp[i-1][...]（上一行），所以可以用一维数组。但必须从右往左遍历，否则会用到已经被当前行覆盖的值：
def knapsack_01_optimized(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for j in range(W, w - 1, -1): # 从右往左！
dp[j] = max(dp[j], dp[j-w] + v)
return dp[W]
为什么从右往左？ 如果从左往右，dp[j-w] 可能已经在本轮被更新过（相当于物品 i 被选了多次）。从右往左保证 dp[j-w] 还是上一轮的值，每个物品最多选一次。
27.7 完全背包问题
和 0-1 背包的区别：每个物品可以选无限次。
def knapsack_complete(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for j in range(w, W + 1): # 从左往右！
dp[j] = max(dp[j], dp[j-w] + v)
return dp[W]
唯一的区别：内层循环从左往右。因为我们允许用到本轮已更新的 dp[j-w]（相当于物品 i 被选了多次）。
零钱兑换就是完全背包：每种硬币可以用无限次，求凑出目标金额的最少硬币数。
| 背包类型 | 每个物品 | 内层循环方向 |
|---|---|---|
| 0-1 背包 | 最多选 1 次 | 从右往左 |
| 完全背包 | 可选无限次 | 从左往右 |
27.8 多重背包问题
每个物品最多选 c[i] 次。
朴素方法：把每个物品拆成 c[i] 个独立物品，然后做 0-1 背包。时间 O(n × W × max(c))。
二进制优化：把 c[i] 个物品拆成 1, 2, 4, 8, ..., 剩余 这几组。例如 c = 13 拆成 1 + 2 + 4 + 6 = 13。这样 13 个物品变成 4 组，用 0-1 背包处理。时间 O(n × W × log(max(c)))。
def knapsack_multi(weights, values, counts, W):
# 二进制拆分
new_w, new_v = [], []
for i in range(len(weights)):
c = counts[i]
k = 1
while k <= c:
new_w.append(weights[i] * k)
new_v.append(values[i] * k)
c -= k
k *= 2
if c > 0:
new_w.append(weights[i] * c)
new_v.append(values[i] * c)
# 转化为 0-1 背包
return knapsack_01_optimized(new_w, new_v, W)
27.9 背包问题变体
方案数问题：不是求最大价值，而是求"有多少种方式恰好装满"。
# 目标和（LeetCode #494）
# 给定数组 nums 和目标 target，每个数字前面加 + 或 -
# 问有多少种方式使得总和等于 target
def find_target_sum_ways(nums, target):
total = sum(nums)
# 转化：正数集合和为 P，负数集合和为 N
# P - N = target, P + N = total → P = (target + total) / 2
if (target + total) % 2 != 0 or abs(target) > total:
return 0
bag = (target + total) // 2
dp = [0] * (bag + 1)
dp[0] = 1 # 空集合，和为 0，有 1 种方式
for num in nums:
for j in range(bag, num - 1, -1): # 0-1 背包
dp[j] += dp[j - num]
return dp[bag]
恰好装满 vs 不超过：
- 不超过：
dp[0] = 0，其余初始化为 0（最大价值问题） - 恰好装满：
dp[0] = 0，其余初始化为-inf（只有恰好装满的状态才有效）
Level 3 · 规范怎么定义的
27.10 动态规划的历史
"Dynamic Programming" 这个名字是 Richard Bellman 在 1953 年在 RAND Corporation 工作时提出的。Bellman 后来解释了为什么选这个名字：
"I chose the name 'dynamic programming' to hide the mathematical nature of my work... The word 'programming' was used in the sense of 'planning' (like military programming), and 'dynamic' was chosen because it sounded impressive and had no precise meaning that could be used against me."
他当时的上司是美国国防部长 Charles Erwin Wilson，此人"对任何包含'研究'字眼的东西都持病态般的恐惧和仇恨"。所以 Bellman 用了一个听起来很厉害但又说不清楚的名字来保护他的研究经费。
Bellman 的核心贡献是 Bellman 方程（也叫最优性原则）：
"An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision."
翻译：最优策略的任何子策略也必须是最优的。 这就是"最优子结构"的正式表述。
27.11 DP 与贪心的关系
贪心（第 26 章）可以看作 DP 的特例：当每一步的局部最优选择恰好就是全局最优时，不需要考虑所有子问题，直接贪心即可。
| 特性 | DP | 贪心 |
|---|---|---|
| 考虑所有选择 | 是 | 否（只选局部最优） |
| 需要证明正确性 | 不需要（穷举所有方案） | 需要（交换论证/反证法） |
| 时间复杂度 | 通常较高 | 通常较低 |
| 适用范围 | 广（只要有最优子结构+重叠子问题） | 窄（需要贪心选择性质） |
例子：零钱兑换如果面额是 [1, 5, 10, 25]（美国硬币），贪心（先用大面额）是正确的。但如果面额是 [1, 3, 4]，凑 6 元时贪心选 4+1+1=3 枚，DP 选 3+3=2 枚。贪心失败了。
27.12 最优子结构的严格定义
设问题 P 的最优解是 S*。如果 S* 可以分解为子问题 P₁, P₂, ..., Pₖ 的解 S₁*, S₂*, ..., Sₖ*，且每个 Sᵢ* 都是子问题 Pᵢ 的最优解，则 P 具有最优子结构。
证明方法（剪贴法/Cut-and-Paste）：反证法。假设某个子问题 Pᵢ 的解 Sᵢ* 不是最优的，那么存在更优的 Sᵢ'。用 Sᵢ' 替换 Sᵢ* 后，原问题的解会变得更优，与 S* 是最优解矛盾。
这个证明方法来自 CLRS（Cormen, Leiserson, Rivest, Stein）的《算法导论》第 15 章。
27.13 状态数与计算量
DP 的时间复杂度 = 状态数 × 每个状态的转移代价。
| 问题 | 状态数 | 转移代价 | 总复杂度 |
|---|---|---|---|
| 爬楼梯 | O(n) | O(1) | O(n) |
| 0-1 背包 | O(nW) | O(1) | O(nW) |
| LIS | O(n) | O(n) | O(n²) |
| 编辑距离 | O(nm) | O(1) | O(nm) |
| 矩阵链乘法 | O(n²) | O(n) | O(n³) |
注意 0-1 背包的 O(nW) 是伪多项式时间（pseudo-polynomial）：W 是数值大小，不是输入长度。如果 W 用 b 位二进制表示，那么 W = 2^b，时间 O(n × 2^b) 是指数级的。这就是为什么背包问题是 NP-hard 的（详见第 37 章复杂度理论）。
Level 4 · 边界与陷阱
27.14 常见的状态定义错误
错误 1：状态维度不够
# 股票买卖（LeetCode #121）— 错误的状态定义
# dp[i] = 第 i 天能获得的最大利润？
# 问题：不知道是否持有股票
# 正确：dp[i][0] = 第 i 天不持有股票的最大利润
# dp[i][1] = 第 i 天持有股票的最大利润
def max_profit(prices):
n = len(prices)
if n < 2:
return 0
dp = [[0, 0] for _ in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) # 卖出
dp[i][1] = max(dp[i-1][1], -prices[i]) # 买入（只能买一次）
return dp[n-1][0]
错误 2：遍历方向错误
0-1 背包内层从右往左，完全背包内层从左往右。弄反了就变成了另一个问题。
错误 3：初始条件遗漏
# 解码方法（LeetCode #91）
# "12" 可以解码为 "AB" 或 "L"
def num_decodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # 空串有 1 种解码方式（这个初始条件容易忘）
dp[1] = 1
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if 1 <= one <= 9:
dp[i] += dp[i-1]
if 10 <= two <= 26:
dp[i] += dp[i-2]
return dp[n]
27.15 空间优化的通用技巧
滚动数组：当 dp[i] 只依赖 dp[i-1] 和 dp[i-2] 时，用两个变量代替整个数组。
# 通用模板
prev2, prev1 = initial_0, initial_1
for i in range(2, n + 1):
curr = f(prev1, prev2)
prev2, prev1 = prev1, curr
二维降一维：当 dp[i][j] 只依赖 dp[i-1][...] 时，去掉第一个维度，注意遍历方向。
27.16 面试高频题
题目 1：最小路径和（LeetCode #64）
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] = dp[0] + grid[i][0]
for j in range(1, n):
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
return dp[n-1]
题目 2：单词拆分（LeetCode #139）
def word_break(s, word_dict):
words = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # 空串可以被拆分
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]
题目 3：分割等和子集（LeetCode #416）
def can_partition(nums):
total = sum(nums)
if total % 2:
return False
target = total // 2
# 转化为 0-1 背包：能否恰好装满容量为 target 的背包
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for j in range(target, num - 1, -1): # 0-1 背包：从右往左
dp[j] = dp[j] or dp[j - num]
return dp[target]
这道题完美展示了问题转化的能力：把"能否分成两个等和子集"转化为"能否选出若干数使和恰好为 total/2"，即 0-1 背包的恰好装满问题。
27.17 DP 题的通用解题框架
当你面对一个新的 DP 题时，按以下步骤思考：
- 确定状态：dp[i] 或 dp[i][j] 代表什么？通常是"以 i 结尾的"或"前 i 个元素的"最优解
- 找转移方程：dp[i] 怎么从前面的状态推导出来？有哪些选择（选/不选、从哪里来）？
- 确定初始条件：最小的子问题答案是什么？
- 确定遍历方向：保证计算 dp[i] 时，它依赖的状态都已经算好了
- 确定返回值：是 dp[n]、max(dp)、还是 dp[n][m]？
- 空间优化（可选）：能否降维？
面试时手动走一遍小例子验证转移方程的正确性，比盯着代码想要可靠得多。
本章小结
| 概念 | 要点 |
|---|---|
| DP 核心 | 重叠子问题 + 最优子结构 → 存结果复用 |
| 学习路径 | 暴力递归 → 发现重复 → 记忆化 → 自底向上 → 空间优化 |
| 三要素 | 状态定义、转移方程、初始条件 |
| 0-1 背包 | 每个物品选一次，内层从右往左 |
| 完全背包 | 每个物品选无限次，内层从左往右 |
| 多重背包 | 二进制优化拆分 + 0-1 背包 |
| 伪多项式 | O(nW) 看起来多项式，但 W 是数值不是输入长度 |
| 面试策略 | 先记忆化写对，再优化为自底向上 |
练习题：
- 零钱兑换 II（LeetCode #518）：给定硬币面额和总金额，求有多少种不同的凑法。（提示：完全背包 + 方案数）
- 整数拆分（LeetCode #343）：将正整数 n 拆分为至少两个正整数的和，求这些整数的最大乘积。
- 最长回文子串（LeetCode #5）：用 DP 解决，并对比 Manacher 算法。
- 把本章的 0-1 背包改成输出具体选了哪些物品（不只是最大价值）。
下一章预告：第 28 章将进入二维 DP——编辑距离、最长公共子序列、区间 DP。这些问题的状态定义从一维扩展到二维，转移方程更复杂，但核心思想完全一样。