w wyl123ly 的博客
MD

算法-动态规划与贪心

55 KB 2026.10.11 原文件

算法-动态规划与贪心

这篇笔记讲什么

动态规划(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 第一步:状态定义的方法论

四问法(按顺序问自己):

  1. 题目要什么? 把答案写成一个函数形式,例如「前 个物品在容量 下的最大价值」→ 提示状态形如 dp[n][W]。
  2. 最后一步的决策是什么? 这是最关键的一问。爬到第 级的最后一步只能是「从 迈 1 级」或「从 迈 2 级」;背包里最后一个物品只能是「放」或「不放」。把最后一步的候选项列出来,转移方程的骨架就有了。
  3. 做完这个决策后,还剩下什么子问题? 剩下的必须仍是同型问题,且规模更小。
  4. 需要额外记住哪些信息?(是否需要「上一家偷没偷」「容量还剩多少」「当前在哪个城市」)→ 这些就是状态的额外维度。

维度的常见来源:

维度含义典型题
下标 / 前缀长度处理到第几个元素爬楼梯、最大子数组和
容量 / 资源余量还剩多少可用资源背包
已用次数 / 阶段用了几次操作、走到第几步买卖股票(含冷冻期)、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 表填表过程():

012345
dp[i]112358

第 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]):

01234
nums[i]27931
偷第 家——dp[0]+9=11dp[1]+3=10dp[2]+1=12
不偷第 家——dp[1]=7dp[2]=11dp[3]=11
dp[i]27111112

答案 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]):

012345678
nums[i]-21-34-121-54
f[i-1]+nums[i]—-1-2135615
f[i](取较大)-21-2435615
best-211445666

答案 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。

01234
0(无物品)00000
1()015151515
2()015152035
3()015152035

第 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]
初始00000
处理物品 1()015151515
处理物品 2()015152035

完全背包(正序)处理物品 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](只填 )。

01234
012334
1—1223
2——113
3———11
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长度
100(空表,追加)[10]1
90(替换)[9]1
20(替换)[2]1
51(追加)[2, 5]2
31(替换)[2, 3]2
72(追加)[2, 3, 7]3
1013(追加)[2, 3, 7, 101]4
183(替换)[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"):

""ace
""0000
a0111
b0111
c0122
d0122
e0123

答案 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. 因为 的右端点最小,必有 。
  3. 用 替换 ,得到 。由于 , 与 不重叠,因此 仍是合法解,且 。
  4. 对剩下的区间重复上述替换,每一步都能把最优解逐步「改造成」贪心解而不减少区间数量,故贪心解至少与最优解一样大,即贪心最优。

为什么排序键必须是右端点,而不是左端点或长度?

- 按左端点排序会失败:区间 、、。贪心先选 ,只能得 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∞∞∞∞∞∞∞∞∞∞∞
硬币 101234567891011
硬币 2011223344556
硬币 5011221223323

最后一步验算: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-索引 / 学习路线图:回到总导航安排学习顺序

参考来源