算法-动态规划与贪心
这篇笔记讲什么
动态规划(Dynamic Programming, DP) 和贪心(Greedy) 都是「把大问题拆成小问题」的最优化方法,区别在于 DP 保留所有候选,贪心每步只赌一个最优选择。
本篇给出 DP 的判定三条件(最优子结构 / 无后效性 / 重叠子问题)、五步法(状态定义 → 转移方程 → 边界 → 遍历顺序 → 空间优化)与状态定义的方法论,覆盖线性 DP、背包、区间 DP、序列 DP、树形 DP、状压 DP 与两类优化;贪心部分给出贪心选择性质与两种正确性证明(交换论证法、归纳法)以及五类经典题。
读完你应该能:拿到一道最优化题先判断「该 DP 还是该贪心」,再按五步法把状态和转移写出来。
一、是什么
动态规划:把原问题分解为相互重叠的子问题,每个子问题只求解一次并把结果存表,后续用常数时间查表,从而用多项式时间解决暴力搜索指数级的问题。它本质上是对决策过程的建模:状态描述「当前所处的局面」,转移描述「从一个局面走一步到另一个局面」。
贪心:在每一步决策时,都选择当前看来最优的那个选项,且永不后悔(不回溯、不保留其他候选)。它比 DP 快得多,但只在问题满足贪心选择性质时正确。
二、为什么需要它 / 什么时候能用 DP
2.1 三个必要条件(缺一不可)
DP 的判定三条件
1. 最优子结构(Optimal Substructure):原问题的最优解包含子问题的最优解。
2. 无后效性(No Aftereffect):一旦状态确定,后续决策只依赖该状态本身,与「如何到达这个状态」的路径无关。
3. 重叠子问题(Overlapping Subproblems):不同分支会反复求解相同的子问题——这正是 DP 相对分治的收益来源。
(1)最优子结构:以无权图最短路径为例。
若从 到 的最短路经过 ,那么 的这段一定是 到 的最短路——否则用更短的一段替换就得到更短的 路径,矛盾。
反例:最长简单路径
求「两点的最长简单路径(不重复顶点)」不满足最优子结构: 的最长简单路与 的最长简单路拼起来可能重复经过同一个顶点,因而不是合法的简单路径。同一类问题换个约束就从「有最优子结构」变成「没有」,所以看到「最长」二字不要条件反射地写 DP。
(2)无后效性:以爬楼梯为例。
状态 dp[i] 定义为「到达第 级台阶的方案数」。从 往后的走法只与「我现在在第 级」有关,与「我是从 还是 迈上来的」无关——这就是无后效性。
反例:状态描述不完整导致有后效性
打家劫舍中,如果状态只定义成
dp[i] = 前 i 家的最大金额,转移时你需要知道「第 家到底偷没偷」才能决定第 家能不能偷。信息缺失会让状态「有后效」。修法有两种:把状态扩成dp[i][0/1](第 家偷/不偷),或者换一个等价但信息完整的定义dp[i] = 考虑前 i 家、且已经做出决策后的最大金额并写成dp[i] = max(dp[i-1], dp[i-2] + a[i])。「无后效性」不是问题的属性,而是你的状态定义是否合格的判据。
(3)重叠子问题:以斐波那契为例。
朴素递归 的递归树中, 被计算两次、 三次……总调用次数是指数级:
而 只有 种不同的参数取值。把重复的参数缓存起来,复杂度立刻降到 ——这就是 DP 的全部收益来源。
与分治的分界线
分治能用的前提是子问题相互独立(归并排序的左右两半互不影响)。一旦子问题重叠,分治就退化成暴力,必须用 DP / 记忆化搜索。反之,如果子问题完全不重叠,DP 的表格里会有大量永远用不到的状态,徒增开销。
2.2 记忆化搜索与递推的互相转换
两者共享同一套「状态 + 转移方程」,只是遍历方向相反:
from functools import lru_cache
def fib_memo(n):
"""自顶向下:记忆化搜索。只计算真正被访问到的状态。"""
@lru_cache(maxsize=None)
def f(k):
if k <= 1:
return k # 边界:base case
return f(k - 1) + f(k - 2) # 转移方程
return f(n)
def fib_tab(n):
"""自底向上:递推填表。需要自己确定遍历顺序。"""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1 # 边界初始化
for i in range(2, n + 1): # 从小到大,保证依赖已就绪
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def fib_roll(n):
"""滚动变量:把 O(n) 空间压到 O(1)"""
if n <= 1:
return n
prev, cur = 0, 1
for _ in range(2, n + 1):
prev, cur = cur, prev + cur
return cur
转换口诀:记忆化搜索的 f(k) 依赖 f(k-1)、f(k-2),说明状态依赖是「小下标依赖更小下标」,所以递推时从小到大遍历。反之若 f(k) 依赖 f(k+1),递推就要从大到小。遍历顺序 = 把状态依赖图做一次拓扑排序。
三、核心内容:五步法解题框架
DP 五步法
① 状态定义 → ② 转移方程 → ③ 边界条件 → ④ 遍历顺序 → ⑤ 空间优化
90% 的 DP 题卡在第 ① 步。后四步都是机械劳动,只有状态定义需要创造力。
3.1 第一步:状态定义的方法论
四问法(按顺序问自己):
- 题目要什么? 把答案写成一个函数形式,例如「前 个物品在容量 下的最大价值」→ 提示状态形如
dp[n][W]。 - 最后一步的决策是什么? 这是最关键的一问。爬到第 级的最后一步只能是「从 迈 1 级」或「从 迈 2 级」;背包里最后一个物品只能是「放」或「不放」。把最后一步的候选项列出来,转移方程的骨架就有了。
- 做完这个决策后,还剩下什么子问题? 剩下的必须仍是同型问题,且规模更小。
- 需要额外记住哪些信息?(是否需要「上一家偷没偷」「容量还剩多少」「当前在哪个城市」)→ 这些就是状态的额外维度。
维度的常见来源:
| 维度 | 含义 | 典型题 |
|---|---|---|
| 下标 / 前缀长度 | 处理到第几个元素 | 爬楼梯、最大子数组和 |
| 容量 / 资源余量 | 还剩多少可用资源 | 背包 |
| 已用次数 / 阶段 | 用了几次操作、走到第几步 | 买卖股票(含冷冻期)、K 站中转 |
| 二值标记(0/1) | 上一个位置选没选 | 打家劫舍、树形 DP |
| 区间端点 | 处理的是一段连续区间 | 最长回文子序列、石子合并 |
| 集合掩码 mask | 已经访问过哪些元素 | 旅行商问题(TSP) |
| 树节点 | 以 为根的子树 | 树上最大独立集 |
两个自检问题:
- 完备性:给出一个状态,能否唯一确定「接下来能做什么」?若不能,说明维度少了。
- 无冗余:两个不同状态是否描述同一局面?若是,说明维度多了,可以合并降复杂度。
3.2 第二至五步:机械四步
| 步骤 | 要做什么 | 常见错误 |
|---|---|---|
| ② 转移方程 | 枚举最后一步的所有决策,取 max / min / sum | 漏掉某个决策分支;把 max 写成 + |
| ③ 边界条件 | 初始化 dp[0]、dp[i][0];处理「不合法状态」 | 用 0 表示不可达,与「价值为 0」混淆;应使用 |
| ④ 遍历顺序 | 保证计算 dp[i] 时它依赖的状态已经算好 | 区间 DP 忘了按长度递增;01 背包一维写法忘了倒序 |
| ⑤ 空间优化 | 滚动数组、维度压缩、去掉无用维度 | 压缩后遍历方向搞错,把「每件物品一次」变成「无限次」 |
四、怎么用:从线性 DP 到状压 DP
4.1 线性 DP
(1)爬楼梯(LeetCode 70)
- 状态:
dp[i]= 到达第 级台阶的方案数。 - 转移:最后一步要么迈 1 级,要么迈 2 级 →
dp[i] = dp[i-1] + dp[i-2]。 - 边界:
dp[0] = 1(地面,一种「什么都不做」的方案)、dp[1] = 1。 - 顺序: 从小到大。
- 空间:只依赖前两项 → 滚动变量 。
def climb_stairs(n):
"""LeetCode 70 爬楼梯:dp[i] = dp[i-1] + dp[i-2]"""
if n <= 2:
return n
a, b = 1, 2 # dp[1], dp[2]
for _ in range(3, n + 1):
a, b = b, a + b
return b
DP 表填表过程():
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
dp[i] | 1 | 1 | 2 | 3 | 5 | 8 |
第 3 级 = dp[2] + dp[1] = 2 + 1 = 3;第 4 级 = dp[3] + dp[2] = 3 + 2 = 5;第 5 级 = 5 + 3 = 8。
(2)打家劫舍(LeetCode 198)
- 状态:
dp[i]= 考虑前 家(下标 )能偷到的最大金额,且已经决定完第 家。 - 转移:第 家偷 → 第 家必须不偷,收益
dp[i-2] + nums[i];第 家不偷 →dp[i-1]。
- 边界:
dp[0] = nums[0],dp[1] = max(nums[0], nums[1])。
def rob(nums):
"""LeetCode 198 打家劫舍:不能偷相邻两家"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1]) # dp[i-2], dp[i-1]
for i in range(2, len(nums)):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
DP 表填表过程(nums = [2, 7, 9, 3, 1]):
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
nums[i] | 2 | 7 | 9 | 3 | 1 |
| 偷第 家 | — | — | dp[0]+9=11 | dp[1]+3=10 | dp[2]+1=12 |
| 不偷第 家 | — | — | dp[1]=7 | dp[2]=11 | dp[3]=11 |
dp[i] | 2 | 7 | 11 | 11 | 12 |
答案 12(偷第 0、2、4 家:)。
(3)最大子数组和(LeetCode 53,Kadane 算法)
- 状态:
f[i]= 以nums[i]结尾的最大子数组和。「以 结尾」这四个字是关键——它保证了无后效性,也让答案变成 。 - 转移:
f[i] = max(nums[i], f[i-1] + nums[i]):要么接在前面,要么从自己重新开始。
def max_subarray(nums):
"""LeetCode 53 最大子数组和。时间 O(n),空间 O(1)"""
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x) # 接上前面更好,还是从自己重新开始?
best = max(best, cur) # 答案不一定是最后一格,必须全程记录
return best
DP 表填表过程(nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
nums[i] | -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 |
f[i-1]+nums[i] | — | -1 | -2 | 1 | 3 | 5 | 6 | 1 | 5 |
f[i](取较大) | -2 | 1 | -2 | 4 | 3 | 5 | 6 | 1 | 5 |
best | -2 | 1 | 1 | 4 | 4 | 5 | 6 | 6 | 6 |
答案 6,对应子数组 (下标 )。
「以 i 结尾」是个万能的状态定义技巧
当题目要求「连续子数组 / 子串」时,把状态定义成「以 结尾」几乎总是对的,因为连续性被编码进了状态本身。若定义成「前 个元素中的最优」,转移时无法判断能否继续延伸,就产生了后效性。
4.2 背包问题
背包是最能体现「状态定义 + 遍历顺序」耦合关系的一类 DP。
(1)0/1 背包: 件物品,第 件重 、价值 ,背包容量 ,每件最多取一次,求最大总价值。
- 状态:
dp[i][j]= 只考虑前 件物品、容量为 时的最大价值。 - 转移:第 件只有「放」与「不放」两种决策。
- 边界:
dp[0][j] = 0(没有物品可选时价值为 0)、dp[i][0] = 0。 - 顺序: 从小到大, 任意(二维写法下顺序无关)。
- 复杂度: 时间、 空间。
def knapsack_01(weights, values, capacity):
"""0/1 背包(二维)。dp[i][j] = 前 i 件、容量 j 的最大价值"""
n = len(weights)
dp = [[0] * (capacity + 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(capacity + 1):
dp[i][j] = dp[i - 1][j] # 决策一:不放
if j >= w: # 决策二:放得下才放
dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v)
return dp[n][capacity]
DP 表填表过程:weights = [1, 3, 4],values = [15, 20, 30],capacity = 4。
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0(无物品) | 0 | 0 | 0 | 0 | 0 |
| 1() | 0 | 15 | 15 | 15 | 15 |
| 2() | 0 | 15 | 15 | 20 | 35 |
| 3() | 0 | 15 | 15 | 20 | 35 |
第 2 行第 4 列:max(dp[1][4]=15, dp[1][4-3]+20 = 15+20 = 35) = 35。第 3 行第 4 列:max(35, dp[2][0]+30 = 30) = 35。答案 35(取物品 1 与 2)。
(2)一维写法:倒序与正序的原理
把 dp[i][j] 压掉第一维后得到 dp[j]。关键问题:计算 dp[j] 时用到的 dp[j-w] 应该是「上一轮(还没考虑第 件)」还是「本轮(已经考虑过第 件)」的值?
| 问题 | 遍历方向 | dp[j-w] 的语义 | 效果 |
|---|---|---|---|
| 0/1 背包 | 从大到小 | 尚未被第 件更新 → 相当于 dp[i-1][j-w] | 第 件只用一次 |
| 完全背包 | 从小到大 | 已被第 件更新 → 相当于 dp[i][j-w] | 第 件可用无限次 |
一句话记住
倒序 = 用旧值(每件一次),正序 = 用新值(每件无限)。 因为
j从小往大走时,小的j已经被本轮更新过;从大往小走时,j-w还没被本轮碰到,仍是上一行的值。
def knapsack_01_1d(weights, values, capacity):
"""0/1 背包一维写法:内层必须倒序,否则同一件物品会被重复使用"""
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
for j in range(capacity, w - 1, -1): # 倒序!
dp[j] = max(dp[j], dp[j - w] + v)
return dp[capacity]
def knapsack_complete(weights, values, capacity):
"""完全背包:每件物品无限次。内层正序即可"""
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
for j in range(w, capacity + 1): # 正序!
dp[j] = max(dp[j], dp[j - w] + v)
return dp[capacity]
一维数组的填表过程:weights = [1, 3],values = [15, 20],capacity = 4。
0/1 背包(倒序):
| 阶段 | dp[0] | dp[1] | dp[2] | dp[3] | dp[4] |
|---|---|---|---|---|---|
| 初始 | 0 | 0 | 0 | 0 | 0 |
| 处理物品 1() | 0 | 15 | 15 | 15 | 15 |
| 处理物品 2() | 0 | 15 | 15 | 20 | 35 |
完全背包(正序)处理物品 1 后:dp = [0, 15, 30, 45, 60]——同一件物品被叠加了 4 次;处理物品 2 后 dp[4] = max(60, dp[1]+20 = 35) = 60,答案 60(拿 4 次物品 1)。
(3)多重背包:第 件最多取 次。
朴素做法是把第 件复制成 件做 0/1 背包,复杂度 。用二进制拆分把 拆成 若干「打包物品」,任取若干包的和可以表示 中的任何数量,物品数降到 :
def knapsack_multiple(weights, values, counts, capacity):
"""多重背包:第 i 件最多 counts[i] 次。二进制拆分 → 0/1 背包"""
items = [] # 拆成若干「打包」物品
for w, v, c in zip(weights, values, counts):
k = 1
while c > 0:
take = min(k, c) # 依次拆出 1, 2, 4, ... 与余数
items.append((w * take, v * take))
c -= take
k <<= 1
dp = [0] * (capacity + 1)
for w, v in items:
for j in range(capacity, w - 1, -1): # 打包物品之间是 0/1 关系
dp[j] = max(dp[j], dp[j - w] + v)
return dp[capacity]
三种背包对比:
| 类型 | 每件可用次数 | 一维内层方向 | 复杂度 | 典型题 |
|---|---|---|---|---|
| 0/1 背包 | 1 次 | 倒序 | 分割等和子集、目标和 | |
| 完全背包 | 无限次 | 正序 | 零钱兑换、完全平方数 | |
| 多重背包 | 次 | 拆包后倒序 | 有限库存的采购方案 |
4.3 区间 DP
适用信号:答案由「一段连续区间」决定,且大区间的解由两个相邻子区间合并而来。
通用形式:
遍历顺序是区间 DP 的第一大坑: 依赖长度更短的区间,所以必须按区间长度 从小到大枚举,而不是简单地 从小到大。
(1)最长回文子序列(LeetCode 516)
- 状态:
dp[i][j]= 子串 的最长回文子序列长度。 - 转移:看两端字符是否相等。
def longest_palindrome_subseq(s):
"""LeetCode 516 最长回文子序列。时间 O(n^2),空间 O(n^2)"""
n = len(s)
if n == 0:
return 0
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1 # 边界:单字符自身是长度 1 的回文
for length in range(2, n + 1): # 关键:按长度递增,短区间先算
for i in range(0, n - length + 1):
j = i + length - 1
if s[i] == s[j]:
# length == 2 时 dp[i+1][j-1] 即 dp[j][i],恒为 0,结果正好是 2
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
DP 表填表过程(s = "bbbab"):表中第 行第 列是 dp[i][j](只填 )。
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 3 | 4 |
| 1 | — | 1 | 2 | 2 | 3 |
| 2 | — | — | 1 | 1 | 3 |
| 3 | — | — | — | 1 | 1 |
| 4 | — | — | — | — | 1 |
验算 dp[0][4]:s[0] = 'b'、s[4] = 'b' 相等 → dp[1][3] + 2 = 2 + 2 = 4。答案 4("bbbb")。
(2)石子合并(洛谷 P1880 链式版)
- 状态:
dp[i][j]= 把第 到第 堆石子合并成一堆的最小总代价。 - 转移:最后一次合并必然把 分成 与 两堆,代价是这两堆的总和。
区间和用前缀和做到 查询,整体复杂度 。
def stone_merge(stones):
"""石子合并(链式):dp[i][j] = min 分割点 + 区间和。O(n^3)"""
n = len(stones)
if n < 2:
return 0
pre = [0] * (n + 1) # 前缀和:pre[k] = a[0] + ... + a[k-1]
for i, x in enumerate(stones):
pre[i + 1] = pre[i] + x
INF = float("inf")
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(0, n - length + 1):
j = i + length - 1
total = pre[j + 1] - pre[i] # 本次合并的代价 = 区间和
dp[i][j] = INF
for k in range(i, j): # 枚举最后一次合并的分割点
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + total)
return dp[0][n - 1]
DP 表填表过程(stones = [1, 3, 5, 2],前缀和 pre = [0,1,4,9,11]):
| 区间 | 长度 | 候选分割点的取值 | dp[i][j] |
|---|---|---|---|
| [0,1] | 2 | 唯一分割: | 4 |
| [1,2] | 2 | 唯一分割: | 8 |
| [2,3] | 2 | 唯一分割: | 7 |
| [0,2] | 3 | ; | 13 |
| [1,3] | 3 | ; | 17 |
| [0,3] | 4 | ;; | 22 |
答案 22(先合并 1 与 3 得 4,再合并 5 与 2 得 7,最后 4+7=11;总代价 )。
环形石子合并
若石子排成环,标准技巧是把数组复制一遍接在后面(长度 ),最后在
dp[i][i+n-1]()中取最优值。这是「环形问题拆成链」的通用套路。
4.4 序列 DP
(1)最长上升子序列 LIS(LeetCode 300)
解法:dp[i] = 以 nums[i] 结尾的 LIS 长度。
def lis_n2(nums):
"""LIS 的 O(n^2) 解法:dp[i] = 以 nums[i] 结尾的最长上升子序列长度"""
if not nums:
return 0
n = len(nums)
dp = [1] * n # 边界:每个元素自己构成长度 1
for i in range(n):
for j in range(i): # 枚举前驱 j
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
解法(耐心排序 + 二分):维护数组 tails,其中 tails[k] = 「所有长度为 的上升子序列中,结尾元素的最小值」。tails 单调不减,因此可以用 bisect_left 二分。
from bisect import bisect_left
def lis_nlogn(nums):
"""LIS 的 O(n log n) 解法。注意 tails 本身不是某个 LIS,只是一个「最优结尾」表"""
tails = []
for x in nums:
pos = bisect_left(tails, x) # 严格上升用 left;允许相等则用 right
if pos == len(tails):
tails.append(x) # x 比所有结尾都大 → LIS 变长
else:
tails[pos] = x # 用小结尾替换大结尾,为后续留出空间
return len(tails)
tails 的演化过程(nums = [10, 9, 2, 5, 3, 7, 101, 18]):
| 处理 | bisect_left 结果 | tails | 长度 |
|---|---|---|---|
| 10 | 0(空表,追加) | [10] | 1 |
| 9 | 0(替换) | [9] | 1 |
| 2 | 0(替换) | [2] | 1 |
| 5 | 1(追加) | [2, 5] | 2 |
| 3 | 1(替换) | [2, 3] | 2 |
| 7 | 2(追加) | [2, 3, 7] | 3 |
| 101 | 3(追加) | [2, 3, 7, 101] | 4 |
| 18 | 3(替换) | [2, 3, 7, 18] | 4 |
答案 4(一个 LIS 是 )。注意最终的 tails = [2,3,7,18] 并不是原数组的上升子序列——这是初学者最常见的误解。
(2)最长公共子序列 LCS(LeetCode 1143)
def longest_common_subsequence(text1, text2):
"""LeetCode 1143 LCS。dp[i][j] = text1[:i] 与 text2[:j] 的 LCS 长度,O(mn)"""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)] # 多一行一列表示「空前缀」
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
DP 表填表过程(text1 = "abcde",text2 = "ace"):
| "" | a | c | e | |
|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 2 | 2 |
| d | 0 | 1 | 2 | 2 |
| e | 0 | 1 | 2 | 3 |
答案 3("ace")。
(3)编辑距离(LeetCode 72)
对 word1 做插入 / 删除 / 替换三种操作,求变成 word2 的最少操作数。
三种操作分别对应:删除 的末字符()、在 末尾插入()、替换末字符()。
def edit_distance(word1, word2):
"""LeetCode 72 编辑距离。时间 O(mn),空间 O(mn)"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # 边界:把 word1[:i] 全删掉
for j in range(n + 1):
dp[0][j] = j # 边界:从空串插入出 word2[:j]
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # 末字符相同,不花代价
else:
dp[i][j] = 1 + min(dp[i - 1][j], # 删除
dp[i][j - 1], # 插入
dp[i - 1][j - 1]) # 替换
return dp[m][n]
4.5 树形 DP
适用信号:决策发生在树的节点上,且子树之间相互独立(这是树形 DP 能成立的根本原因)。
通用做法:后序遍历(DFS)。先递归算出所有子节点的 DP 值,再用它们合并出当前节点的 DP 值——本质上就是「在树上做后序的 DP」。
例题:树上最大独立集 / 打家劫舍 III(LeetCode 337)。状态需要二维,因为父节点的决策依赖「子节点选没选」:
dp[u][0]= 不选 时,以 为根的子树能取得的最大值;dp[u][1]= 选 时的最大值。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def rob_tree(root):
"""LeetCode 337:树上最大独立集。返回 (不选 u, 选 u) 两个值"""
def dfs(u):
if u is None:
return 0, 0 # 空节点:选或不选都是 0
l0, l1 = dfs(u.left)
r0, r1 = dfs(u.right)
# 不选 u:子节点各自取「选或不选」中的较大值
not_take = max(l0, l1) + max(r0, r1)
# 选 u:两个子节点都必须不选
take = u.val + l0 + r0
return not_take, take
return max(dfs(root))
树形 DP 的复杂度
每个节点只被访问一次,合并子节点信息的代价与度数成正比,所以总复杂度是 (若状态有 维则是 )。与「树的形状」无关,链状树和星形树一样快,这是树形 DP 相比图上 DP 的巨大优势。
4.6 状态压缩 DP:旅行商问题(TSP)
当状态的某一维是「一个集合」时,用二进制掩码(bitmask) 把它压进一个整数。典型场景: 的「访问所有点」类问题。
TSP(Traveling Salesman Problem):从城市 0 出发,访问所有城市各一次并回到 0,求最小总路程。Held-Karp 算法的状态:
dp[mask][i]= 已经访问过的城市集合为 、当前停在城市 的最小代价。
复杂度:状态数 ,每次转移枚举 共 种 → 。
def tsp(dist):
"""Held-Karp 求 TSP 最优回路。dist 是 n x n 距离矩阵。O(2^n * n^2)"""
n = len(dist)
INF = float("inf")
full = (1 << n) - 1
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # 只访问了城市 0,当前在 0,代价为 0
for mask in range(1 << n):
for i in range(n):
if dp[mask][i] == INF or not (mask >> i) & 1:
continue # 状态不可达,或 i 不在已访问集合里
for j in range(n):
if (mask >> j) & 1:
continue # j 已经访问过,不能重复访问
nmask = mask | (1 << j)
nd = dp[mask][i] + dist[i][j]
if nd < dp[nmask][j]:
dp[nmask][j] = nd
return min(dp[full][i] + dist[i][0] for i in range(n))
状压 DP 的规模上限
的增长极快: 时状态数是 ,配合 的转移约 次运算,已是 Python 的极限; 就需要 个状态,内存直接爆掉。题目给 就是状压的信号,给 则一定不是状压。
4.7 DP 的两类常用优化
(1)滚动数组:把「只依赖上一层」的维度压掉。以 LCS 为例,dp[i][j] 依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1],压掉第一维后 dp[i-1][j-1] 会被 dp[j-1] 覆盖,必须用一个变量暂存左上角:
def lcs_rolling(a, b):
"""LCS 滚动数组:空间从 O(mn) 降到 O(n)"""
n = len(b)
dp = [0] * (n + 1)
for i in range(1, len(a) + 1):
diag = 0 # 相当于 dp[i-1][j-1]
for j in range(1, n + 1):
tmp = dp[j] # 先存下 dp[i-1][j],它就是下一列的「左上」
if a[i - 1] == b[j - 1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j - 1])
diag = tmp
return dp[n]
(2)前缀和优化:当转移是「对一段连续状态求和 / 求最值」时,用前缀和把每次转移从 降到 。
例:每次可以跳 级台阶,求到达第 级的方案数。
其中 是前缀和。复杂度从 降到 :
def jump_ways(n, k):
"""每次跳 1..k 级,求到第 n 级的方案数。前缀和把 O(nk) 优化到 O(n)"""
MOD = 10 ** 9 + 7
dp = [0] * (n + 1)
pre = [0] * (n + 2) # pre[i] = dp[0] + ... + dp[i-1]
dp[0] = 1
pre[1] = 1
for i in range(1, n + 1):
lo = max(0, i - k)
dp[i] = (pre[i] - pre[lo]) % MOD # 区间和 O(1) 得到
pre[i + 1] = (pre[i] + dp[i]) % MOD
return dp[n]
| 优化手段 | 适用信号 | 收益 |
|---|---|---|
| 滚动数组 | 状态只依赖上一层 / 上若干层 | 空间 |
| 前缀和 | 转移是连续区间的和 | 时间 |
| 单调队列 | 转移是滑动窗口最值 | 时间 |
| 二分 + 贪心(LIS) | 转移是「找第一个满足条件的前驱」 | 时间 |
| 二进制拆分(多重背包) | 同类物品有多次限额 | 物品数 |
五、贪心
5.1 贪心与 DP 的区别
| 维度 | 动态规划 | 贪心 |
|---|---|---|
| 每步决策 | 保留所有候选,取最优 | 只选当前看起来最好的,不回头 |
| 依赖的性质 | 最优子结构 + 无后效性 + 重叠子问题 | 最优子结构 + 贪心选择性质 |
| 是否回看历史 | 需要(状态里编码了历史信息) | 不需要(历史信息被压缩成一个标量,如「当前右端点」) |
| 时间 | 通常 、 等多项式 | 通常 (排序主导) |
| 正确性 | 由状态定义的完备性保证 | 必须额外证明,很容易想当然地错 |
| 典型失败 | 状态有后效性 | 局部最优 ≠ 全局最优 |
贪心选择性质(Greedy Choice Property)
每一步做出的局部最优选择,一定存在于某个全局最优解中。换句话说:做完这次贪心选择后,剩下的问题仍能拼出全局最优。这个性质必须证明,不能靠感觉。「交换论证法」就是证明它的标准工具。
5.2 如何证明贪心正确性
(1)交换论证法(Exchange Argument)——以区间调度为例
问题:给定若干区间,选出尽可能多的互不重叠的区间。
贪心策略:把所有区间按右端点升序排序,依次扫描,只要能放就放。
证明:
- 设按右端点排序后贪心选中的第一个区间是 ,它是所有区间中右端点最小的。设某个最优解为 (也按右端点排序)。
- 因为 的右端点最小,必有 。
- 用 替换 ,得到 。由于 , 与 不重叠,因此 仍是合法解,且 。
- 对剩下的区间重复上述替换,每一步都能把最优解逐步「改造成」贪心解而不减少区间数量,故贪心解至少与最优解一样大,即贪心最优。
为什么排序键必须是右端点,而不是左端点或长度?
- 按左端点排序会失败:区间 、、。贪心先选 ,只能得 1 个,最优是 2 个。
- 按长度排序会失败:、、 长度分别是 4、1、1,按长度先选 ,则 也能选(2 个),但如果换成 、、,按长度先选 ,再选 ,恰好 2 个——然而加上 就冲突了。真正的失败例子是 、、、:按长度排序先选 、,得 2 个;最优是 、 之外还能选…… 关键结论是:右端点是唯一能使「剩余可用空间最大」的键,这才是交换论证能走通的原因。
(2)归纳法——以加油站为例
问题(LeetCode 134):环形路线上有 个加油站,第 站可加油
gas[i],从第 站到第 站耗油cost[i]。求能绕行一圈的起始站编号(保证唯一),无解返回 。贪心策略:若 则无解;否则从「累积油量首次跌到负数」的下一站重新开始,最后剩下的起点就是答案。
证明:令 ,前缀和 。
- 归纳基础:若 ,任何起点的总油量都不够,无解。命题成立。
- 归纳假设:设贪心在扫描到 时油箱见底(
tank < 0),则对任意起点 ,从 出发都无法到达 。因为到达 需要 ,而贪心已从某个更早的 重置,使得 ;由于 时 不一定成立…… 严格地说,我们需要的是:若从 到 中途油箱从未见底,那么任何 作为起点都无法到达 ——这是因为从 出发的油量是 ,而 意味着 ( 是重置点,其前缀和是当前最小值),于是 。 - 归纳结论:重置点之后的前缀和是整个数组的最小值,因此从该点出发,任意位置 处的剩余油量为 ,全程不会见底,贪心起点正确。
def can_complete_circuit(gas, cost):
"""LeetCode 134 加油站。O(n) 时间、O(1) 空间"""
if sum(gas) < sum(cost):
return -1 # 总油量不足,必无解
start, tank = 0, 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0: # 从 start..i 出发都到不了 i+1
start = i + 1 # 起点至少是 i+1
tank = 0 # 油箱清零,重新累积
return start
5.3 经典贪心问题
(1)区间调度 / 无重叠区间(LeetCode 435)
def erase_overlap_intervals(intervals):
"""LeetCode 435 无重叠区间:按右端点排序,能留就留,返回需要移除的最少个数"""
if not intervals:
return 0
intervals = sorted(intervals, key=lambda x: x[1]) # 关键:按右端点升序
kept, last_end = 0, float("-inf")
for s, e in intervals:
if s >= last_end: # 与上一个选中的区间不重叠
kept += 1
last_end = e # 更新「已用到的最右位置」
return len(intervals) - kept
(2)跳跃游戏(LeetCode 55 / 45)
def can_jump(nums):
"""LeetCode 55 跳跃游戏:维护能到达的最远下标。O(n)"""
reach = 0
for i, step in enumerate(nums):
if i > reach: # 当前位置都到不了,后面更到不了
return False
reach = max(reach, i + step)
if reach >= len(nums) - 1:
return True
return True
def jump_min(nums):
"""LeetCode 45 跳跃游戏 II:求最少跳跃次数。按「层」推进,O(n)"""
n = len(nums)
steps = end = farthest = 0
for i in range(n - 1): # 最后一个位置不需要再起跳
farthest = max(farthest, i + nums[i])
if i == end: # 走到了当前层的边界,必须再跳一次
steps += 1
end = farthest # 下一层的最远边界
return steps
(3)分发糖果(LeetCode 135):需要两次贪心——因为「比邻居评分高」这个约束是双向的,一次扫描只能处理一个方向。
def candy(ratings):
"""LeetCode 135 分发糖果:左右各扫一遍,取两个方向的较大值。O(n)"""
n = len(ratings)
candies = [1] * n # 每人至少 1 颗
for i in range(1, n): # 左→右:满足「比左边评分高」
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1): # 右→左:满足「比右边评分高」
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)
(4)哈夫曼编码(Huffman Coding):每次合并频率最小的两棵子树。贪心选择性质保证了加权外部路径长度(WPL)最小,即编码后的总长度最短,这也是 的最优前缀码构造。
import heapq
def huffman_cost(freqs):
"""哈夫曼编码的最小加权外部路径长度 WPL。O(n log n)"""
if len(freqs) <= 1:
return 0
heap = list(freqs)
heapq.heapify(heap)
total = 0
while len(heap) > 1:
a = heapq.heappop(heap) # 频率最小
b = heapq.heappop(heap) # 频率次小
merged = a + b
total += merged # 每次合并的代价计入总代价
heapq.heappush(heap, merged)
return total
def huffman_codes(freqs):
"""构造哈夫曼编码表,返回 {符号下标: 01 编码}"""
if not freqs:
return {}
heap = [[f, i] for i, f in enumerate(freqs)] # [频率, 节点编号]
heapq.heapify(heap)
nodes = {i: (f, None, None) for i, f in enumerate(freqs)}
counter = len(freqs)
while len(heap) > 1:
a = heapq.heappop(heap)
b = heapq.heappop(heap)
nodes[counter] = (a[0] + b[0], a[1], b[1]) # 合并成新的内部节点
heapq.heappush(heap, [a[0] + b[0], counter])
counter += 1
codes = {}
def dfs(idx, code):
_, left, right = nodes[idx]
if left is None: # 叶子节点
codes[idx] = code or "0" # 只有一个符号时约定为 "0"
return
dfs(left, code + "0")
dfs(right, code + "1")
dfs(heap[0][1], "")
return codes
(5)加油站(LeetCode 134):见 5.2 的归纳法证明与代码。
5.4 同一问题:DP 与贪心解法对比总结
| 问题 | 贪心能得到最优解吗 | 贪心策略 | DP 解法与复杂度 | 说明 / 反例 |
|---|---|---|---|---|
| 分数背包(物品可分割) | ✅ 是 | 按性价比 降序装 | 不需要 | 可分割 ⇒ 交换论证成立 |
| 0/1 背包 | ❌ 否 | 按性价比降序 | 容量 10,物品 :贪心得 30,最优 48 | |
| 零钱兑换(任意币值) | ❌ 否 | 每次用最大面额 | 币值 ,目标 15:贪心 5 枚,最优 3 枚() | |
| 零钱兑换(币值规范,如人民币) | ✅ 是 | 每次用最大面额 | 规范币值系统才成立,需单独证明 | |
| 最长上升子序列 | ✅ 是(配合二分) | 维护「同长度的最小结尾」 | 或 | 贪心 + 二分即 解法 |
| 区间调度 / 无重叠区间 | ✅ 是 | 按右端点排序 | (按结束时间 DP) | 贪心 更优,见 5.2 证明 |
| 跳跃游戏 | ✅ 是 | 维护最远可达 | :dp[i] = 到达 的最少步数 | 贪心 更优 |
| 分发糖果 | ✅ 是 | 左右各扫一遍 | (也可视为双向 DP) | 贪心的「取 max」等价于把两个方向的 DP 合并 |
| 哈夫曼编码 | ✅ 是 | 每次合并最小两个 | (区间 DP 形式) | 贪心 更优 |
| 最长回文子序列 | ❌ 无贪心策略 | — | 区间 DP | 必须 DP |
判断口诀
看到「每个决策会改变后续可选项的范围,且只需要记住一个边界」(如「最右端点」「最远可达」「当前油箱」)→ 先试贪心,再证明。
看到「决策之间有复杂的相互制约,需要记住多个维度的历史」(如「容量还剩多少 + 前一件放没放」)→ 直接用 DP,别浪费时间想贪心。
六、注意事项与常见坑
什么时候不能用动态规划
- 不满足最优子结构:如「最长简单路径」「无容量限制且需求可分割的复杂约束」类问题。判据:能否找到「子问题的最优解拼接起来不是全局最优」的反例。
- 状态无法做到无后效性且无法扩展维度:当「未来决策需要的历史信息」长度随 增长(例如需要知道完整的已访问顺序)时,维度会爆炸,此时应改用搜索、贪心或数学方法。
- 状态空间过大: 中的 若是 (例如容量是 64 位整数),表格开不出来,需要换思路(如数论、贪心、折半枚举)。
- 有环依赖:状态转移互相依赖(如「图上带负环的最短路」)时递推无拓扑序,记忆化搜索会死循环——必须先用 Bellman-Ford 类方法判负环。
- 精度要求极高的浮点 DP:反复
max/min累积的浮点误差可能超过判题容差,此时应改写成整数运算。
什么时候不能用贪心
- 局部最优不等于全局最优:0/1 背包、任意币值的零钱兑换都是经典反例(见表)。
- 贪心选择会「锁死」更优选项:若某个选择事后无法撤销且影响面很大,必须证明它一定在某个最优解中,否则老老实实 DP。
- 题目要求的是方案数、字典序最小的具体方案:贪心只能给出一个最优值,不能给出全部方案。
- 约束是双向的:像分发糖果那样「既要大于左邻居又要大于右邻居」,单次扫描的贪心必须拆成两次,否则会漏解。
其他高频坑
1. DP 数组用
0表示「不可达」:当答案是「最少步数」时,0与「代价为 0」混淆。不可达状态应初始化为 (求 min)或 (求 max)。2. 01 背包一维写法写成正序:结果变成完全背包,样例往往还能过(值更大),是最隐蔽的错误之一。
3. 区间 DP 忘了按长度遍历:按 从小到大遍历会读到还没算的
dp[i+1][j],结果偏小或为 0。4. LIS 的
bisect_left与bisect_right混用:严格上升用left,非严格上升(允许相等)用right。5. 贪心忘了先排序或排序键选错:区间调度按左端点或长度排序都会错。
6. 把「最小值」当「最大值」初始化:求 min 的 DP 若初值为 0,
min永远返回 0。7. 滚动数组覆盖了还需要的旧值:LCS 压成一维时必须用变量暂存左上角
dp[i-1][j-1]。8. 记忆化搜索的参数不可哈希:
lru_cache不能缓存list参数,要改成tuple或把状态编码成整数。
七、练习题
练习 1(完全背包,给出完整解题过程)
LeetCode 322 零钱兑换:给定不同面额的硬币
coins和总金额amount,求凑成总金额所需的最少硬币个数;无法凑成返回-1。每种硬币数量无限。
第一步:判断模型。每种硬币可无限使用 → 完全背包(求最小值而非最大值)。
第二步:五步法。
- ① 状态定义:
dp[j]= 凑出金额 所需的最少硬币个数。最后一步的决策是「最后一枚硬币用哪个面额」。 - ② 转移方程:最后一枚硬币可以是任意面额 ,只要 。
- ③ 边界:
dp[0] = 0(凑 0 元需要 0 枚);其余初始化为 (表示不可达)。 - ④ 遍历顺序:外层枚举硬币(物品),内层正序枚举金额(因为是完全背包)。
- ⑤ 空间优化:本身就是一维,。
第三步:实现。
def coin_change(coins, amount):
"""LeetCode 322 零钱兑换:完全背包求最小值。时间 O(n * amount)"""
INF = float("inf")
dp = [INF] * (amount + 1)
dp[0] = 0 # 边界:凑 0 元需要 0 枚
for c in coins: # 外层物品
for j in range(c, amount + 1): # 内层金额正序 = 完全背包
if dp[j - c] + 1 < dp[j]:
dp[j] = dp[j - c] + 1
return -1 if dp[amount] == INF else dp[amount]
第四步:分步推演。coins = [1, 2, 5],amount = 11:
| 处理完 | dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] | dp[8] | dp[9] | dp[10] | dp[11] |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初始 | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| 硬币 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 硬币 2 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 |
| 硬币 5 | 0 | 1 | 1 | 2 | 2 | 1 | 2 | 2 | 3 | 3 | 2 | 3 |
最后一步验算:dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = min(3, 4, 3) = 3,对应 。
第五步:边界检查。amount = 0 → 返回 0(dp[0] = 0)。coins 为空且 amount > 0 → 全部保持 ,返回 。注意判断「不可达」必须用 dp[amount] == INF,不能写成 dp[amount] == -1,因为我们从未写入 。
为什么这里不能用贪心
若
coins = [1, 5, 11]、amount = 15,贪心会先取 11,剩 4 只能取四个 1,共 5 枚;而最优解是 枚。只有在「规范币值系统」中贪心才正确,一般情况必须 DP。
练习 2(01 背包判定)
LeetCode 416 分割等和子集:判断能否把数组分成两个子集,使两子集元素和相等。
提示:令 。若 为奇数则直接返回 False;否则问题等价于「能否从数组中选出若干个数,使其和恰好为 」——这是一个可行性 01 背包,dp[j] 表示「能否凑出和 」,转移为 dp[j] = dp[j] or dp[j - x],内层倒序。
练习 3(环形 DP / 树形 DP)
LeetCode 213 打家劫舍 II:房屋围成一圈,首尾相邻,不能偷相邻两家。
提示:环形问题的通用拆解——第一家和最后一家不能同时偷,于是分两种情况取最大值:① 只考虑 nums[0..n-2];② 只考虑 nums[1..n-1]。两种情况都是线性打家劫舍。
练习 4(区间 DP)
LeetCode 5 最长回文子串:求最长的回文子串(不是子序列)。
提示:把 516 的 dp[i][j] 语义从「最长回文子序列长度」改成「 是否为回文」,转移为 dp[i][j] = (s[i] == s[j]) and (j - i < 2 or dp[i+1][j-1]),仍按区间长度递增遍历。
练习 5(贪心 + 证明)
LeetCode 452 用最少数量的箭引爆气球:气球用区间 表示,箭沿 轴垂直射出,一支箭可以引爆所有包含该射点坐标的气球,求最少箭数。
提示:与 435 结构相同——按右端点升序排序,若当前气球的左端点大于上一支箭的位置,就必须再射一箭。请仿照 5.2 的交换论证法写出正确性证明。
八、常见问题 FAQ
拿到一道新题,怎么快速判断该用 DP 还是贪心?
按这个顺序问三个问题:① 题目要「最优值 / 方案数」还是「一组具体的解」?方案数基本只能 DP。② 每个决策是否需要记住多个维度的历史(还剩多少容量、上一个选没选)?需要就是 DP。③ 我能否说出一个「只需要记住一个边界」的贪心策略,并给出反例检验?说不出就用 DP。面试时的安全策略是:先用 DP 拿到一个正确但慢的解法,再考虑是否有贪心优化。
DP 数组初始化为 0 还是 / ?
看转移里的运算符:求
max且状态「只能从合法状态转移而来」时,非法状态要设 ,否则它会被当成「价值为 0 的合法状态」污染答案;求min时设 。只有当「0」本身就是合法且最优的取值(例如背包的「什么都不装」)时,才能用 0。最典型的对比是零钱兑换(用 )与 0/1 背包(用 0)。
为什么完全背包是正序、01 背包是倒序?能不能只记结论?
结论要记,但更要理解:一维数组
dp[j]有两个身份——倒序时dp[j-w]是「上一行」(还没考虑当前物品),正序时dp[j-w]是「本行」(已经考虑过当前物品,允许再取一次)。倒序 = 用旧值 = 每件一次;正序 = 用新值 = 每件无限。 理解这一点后,多重背包的二进制拆分、分组背包的循环位置都能自己推出来。
记忆化搜索会栈溢出吗?该怎么处理?
会。CPython 默认递归上限约 1000,链状的 DP(例如 的线性 DP)用记忆化搜索会抛
RecursionError。三种处理:① 改写成递推(首选);② 用显式栈手动模拟递归;③ 谨慎提高sys.setrecursionlimit,但要注意 C 栈的实际限制,调太高会直接段错误。
相关笔记
- 算法-查找与分治:记忆化搜索与分治的对照、二分 + 贪心(LIS 与二分答案)的交汇点
- 算法-复杂度分析:DP 复杂度 = 状态数 × 转移代价,以及主定理在分治递推式上的应用
- 算法-图算法:Dijkstra 与 Bellman-Ford 是「最短路上的 DP」,Floyd 是区间 DP 的近亲
- 算法-排序:贪心几乎总以排序开头,排序键的选择往往就是贪心策略本身
- 数据结构-树与堆:树形 DP 依赖后序遍历,哈夫曼编码依赖优先队列(堆)
- 算法-查找与分治 中的三分查找:与 DP 结合可求单峰型的「最小化最大值」问题
- 00-索引 / 学习路线图:回到总导航安排学习顺序
参考来源
- OI Wiki · 动态规划基础:状态设计、记忆化搜索与递推的中文系统讲解
- OI Wiki · 背包问题:01 / 完全 / 多重背包的推导与优化
- OI Wiki · 记忆化搜索:记忆化搜索与递推的转换
- OI Wiki · 区间 DP:区间 DP 的遍历顺序与四边形不等式优化
- OI Wiki · 树形 DP:树上最大独立集、换根 DP
- OI Wiki · 状态压缩 DP:状压 DP 与 TSP 的经典实现
- OI Wiki · 贪心:贪心选择性质与常见题型
- OI Wiki · 哈夫曼树:哈夫曼编码的构造与最优性
- cp-algorithms · Knapsack Problem:背包问题的英文推导与代码
- cp-algorithms · Longest Increasing Subsequence:LIS 的 解法与正确性说明
- MIT OCW 6.046J Design and Analysis of Algorithms:DP 与贪心的公开课,含交换论证法
- GeeksforGeeks · Travelling Salesman Problem using DP:Held-Karp 状压 DP
- LeetCode 322 零钱兑换 · 416 分割等和子集 · 198 打家劫舍 · 337 打家劫舍 III · 300 最长递增子序列 · 1143 最长公共子序列 · 72 编辑距离 · 516 最长回文子序列 · 435 无重叠区间 · 135 分发糖果 · 134 加油站