Cao Note

外观

动态规划与回溯 ​

DP 是"有重叠子问题的递归 + 记答案"，回溯是"暴力枚举 + 撤销"。前者难在想通状态与转移，后者难在剪枝与去重。

一、动态规划思想 ​

1.1 什么题目用 DP（识别特征） ​

  • 求最优值/方案数/可行性（最大、最小、多少种、能否达成）而不是求具体路径。
  • 问题能分解成子问题，且子问题被重复计算（重叠子问题）。
  • 当前决策只依赖若干"已算好的子状态"（最优子结构）。

1.2 重叠子问题与最优子结构 ​

  • 重叠子问题：朴素递归会重复算同一子问题 → 用表记答案避免重复（斐波那契最典型）。
  • 最优子结构：全局最优能由子问题最优拼出来（最短路径是；"最长简单路径"不是）。

1.3 自顶向下 vs 自底向上 ​

方向写法优点缺点
自顶向下递归 + 备忘录（记忆化搜索）只算用到的状态，代码贴近递推式递归深、有栈溢出风险
自底向上迭代填表（递推）无递归开销、可滚动数组可能算无用状态

二、DP 五步法 ​

2.1 第一步：定义状态 ​

  • 用几个维度刻画"我们正在解决哪个子问题"。例：dp[i] 表示爬到第 i 级台阶的方案数。
  • 状态维度 = 影响答案的独立变量个数（一维/二维/三维）。维度越多空间越大，先想能否压缩。

2.2 第二步：写转移方程 ​

  • 核心一步：dp[i] 如何由更小的 dp[...] 拼出来。用"最后一步"思考法——问题最后一次决策有几种选择。
爬楼梯：最后一步要么从 i-1 迈 1 级，要么从 i-2 迈 2 级
→ dp[i] = dp[i-1] + dp[i-2]
爬楼梯：最后一步要么从 i-1 迈 1 级，要么从 i-2 迈 2 级
→ dp[i] = dp[i-1] + dp[i-2]

2.3 第三步：初始化 ​

  • 找"边界状态"，它们无法由转移得到，需要手工赋值（如 dp[0]、dp[1]）。
  • 常见哨兵技巧：多开一格/多开一行（如 dp = [[0]*(m+1) for _ in range(n+1)]），免去大量越界分支。

2.4 第四步：确定遍历顺序 ​

  • 原则：计算 dp[i] 时，它依赖的状态必须先算好。
  • 一维常见正序；依赖左侧两个的也是正序；依赖"更小规模"的多维要考虑先遍历哪个维度。
  • 滚动数组后要特别注意顺序：0-1 背包倒序、完全背包正序（见 4.2）。

2.5 第五步：举例验证 ​

  • 拿小例子（如 n=4）手推 dp 表，确认转移、初始化、遍历顺序都对，防止「样例过、边界挂」。

2.6 五步法模板 ​

python
# 以爬楼梯为例的通用框架
def solve(n):
    # 1 状态：dp[i]
    dp = [0] * (n + 1)
    # 2 转移：dp[i] = dp[i-1] + dp[i-2]
    # 3 初始化
    dp[0] = dp[1] = 1
    # 4 遍历顺序
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    # 5 返回目标状态
    return dp[n]
# 以爬楼梯为例的通用框架
def solve(n):
    # 1 状态：dp[i]
    dp = [0] * (n + 1)
    # 2 转移：dp[i] = dp[i-1] + dp[i-2]
    # 3 初始化
    dp[0] = dp[1] = 1
    # 4 遍历顺序
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    # 5 返回目标状态
    return dp[n]

三、经典题拆解一：爬楼梯 ​

3.1 分析 ​

  • 状态：dp[i] = 到第 i 级有几种走法；转移：dp[i]=dp[i-1]+dp[i-2]；初始化 dp[0]=1, dp[1]=1。
  • 滚动优化：只需保留前两个值，空间 O(1)。
  • 变体题感：每次可走 1/2/3 步 → 三项和；不能连续走 2 步 → 状态加一维记录"上一步怎么走的"。

3.2 变体：最小花费爬楼梯 ​

  • 状态：cost[i] 从第 i 级出发的最小总花费；dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。
  • 与"方案数"的区别：转移是 min/max 而不是求和 → 求最优值用 min/max，求方案数用累加。

四、经典题拆解二：0-1 背包 ​

4.1 状态与转移 ​

  • 问题：n 个物品，重量 w[i]、价值 v[i]，容量 W，每件最多拿一次，求最大价值。
  • 状态：dp[i][j] = 前 i 个物品、容量 j 的最大价值。
  • 转移（拿或不拿）：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
python
def knapsack(n, W, w, v):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            if j < w[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
    return dp[n][W]
def knapsack(n, W, w, v):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            if j < w[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
    return dp[n][W]

4.2 二维 → 一维滚动数组 ​

  • 每行只依赖上一行 → 压成一维 dp[j]，但容量 j 要倒序遍历，避免本轮物品被重复取。
python
def knapsack_1d(n, W, w, v):
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, w[i] - 1, -1):   # 关键：倒序
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])
    return dp[W]
def knapsack_1d(n, W, w, v):
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, w[i] - 1, -1):   # 关键：倒序
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])
    return dp[W]
  • 判断是否 0-1：倒序；完全背包（无限件）：正序。

4.3 变体：完全背包 / 组合数 ​

  • 完全背包：物品无限，容量正序遍历即可。
  • 求"恰好装满"：初始化 dp[0]=0，其余为 -inf。
  • 求方案数：dp[j] += dp[j-w[i]]；若还要求"不考虑顺序（组合）"先遍历物品、"考虑顺序（排列）"先遍历容量。

五、经典题拆解三：最长递增子序列 LIS ​

5.1 O(n²) DP ​

  • 状态：dp[i] = 以 a[i] 结尾的最长递增子序列长度。
  • 转移：dp[i] = max(dp[j] + 1)，其中 j < i 且 a[j] < a[i]；答案 = max(dp)。
python
def lis(a):
    n = len(a)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)
def lis(a):
    n = len(a)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

5.2 贪心 + 二分 O(n log n)（延伸） ​

  • 维护 tails：长度为 k 的递增子序列的最小结尾；新元素在 tails 上二分找第一个 ≥ 它的位置并替换。
  • 只能求长度，不能还原具体子序列；面试先答 O(n²)，再提可优化到 O(n log n)。

六、经典题拆解四：编辑距离 ​

6.1 状态定义 ​

  • 把 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数：dp[i][j]。
  • 操作：插入、删除、替换，各算 1 次。

6.2 转移与初始化 ​

if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]      # 相同则不动
else: dp[i][j] = min(
        dp[i-1][j] + 1,     # 删除 word1[i-1]
        dp[i][j-1] + 1,     # 插入 word2[j-1]
        dp[i-1][j-1] + 1    # 替换
      )
初始化：dp[i][0] = i（全删）、dp[0][j] = j（全插）
if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]      # 相同则不动
else: dp[i][j] = min(
        dp[i-1][j] + 1,     # 删除 word1[i-1]
        dp[i][j-1] + 1,     # 插入 word2[j-1]
        dp[i-1][j-1] + 1    # 替换
      )
初始化：dp[i][0] = i（全删）、dp[0][j] = j（全插）
  • 复杂度 O(n·m)；滚动数组可压到 O(m) 空间。
  • 同族题：最长公共子序列 LCS（转移只差在不等时取 max 而非 min）。

七、记忆化搜索 vs 递推 ​

7.1 记忆化搜索写法（递归 + 备忘录） ​

python
from functools import lru_cache

@lru_cache(None)
def climb(i):
    if i <= 1: return 1
    return climb(i - 1) + climb(i - 2)
from functools import lru_cache

@lru_cache(None)
def climb(i):
    if i <= 1: return 1
    return climb(i - 1) + climb(i - 2)

7.2 两者对比 ​

维度记忆化搜索（自顶向下）递推（自底向上）
代码可读性贴近自然递归、易写需想清填表顺序
计算范围只算被依赖的状态可能算全部状态
递归栈有（深了溢出）无
适用状态复杂/转移难枚举常规题目首选

7.3 如何选择 ​

  • 二维及以上、转移需要枚举子集、状态"稀疏" → 记忆化更省心。
  • 一维简单题、要求极致性能 → 递推 + 滚动数组。

八、回溯算法框架 ​

8.1 回溯本质（决策树遍历） ​

  • 回溯 = DFS + 撤销：在决策树上做深度优先搜索，走不通/收集到答案就回退。
  • 与 DP 区别：回溯是"穷举所有路径"，DP 是"合并重复子问题"。
全排列决策树（前两层）：
         []
      /  |  \
     1   2   3        ← 第一层选谁
    / \     ...
   2   3              ← 第二层在剩余里选
全排列决策树（前两层）：
         []
      /  |  \
     1   2   3        ← 第一层选谁
    / \     ...
   2   3              ← 第二层在剩余里选

8.2 框架模板（选择 / 撤销） ​

python
def backtrack(路径, 选择列表):
    if 满足结束条件:
        收集答案(路径)          # 注意深拷贝
        return
    for 选择 in 选择列表:
        做选择                  # 加入路径 / 标记 used
        backtrack(路径, 新的选择列表)
        撤销选择                # 移除路径 / 清除 used
def backtrack(路径, 选择列表):
    if 满足结束条件:
        收集答案(路径)          # 注意深拷贝
        return
    for 选择 in 选择列表:
        做选择                  # 加入路径 / 标记 used
        backtrack(路径, 新的选择列表)
        撤销选择                # 移除路径 / 清除 used
  • 三个要点：路径记录已做选择；选择列表决定下一步可选；撤销保证不同分支互不影响。

8.3 剪枝 ​

  • 在进入分支前判断"该分支不可能产生答案/更优答案"就跳过，能大幅提速。
  • 常见剪枝：排序后跳过重复元素、当前和已超目标直接 return、可行性/上界估计（分支限界）。

九、回溯经典题 ​

9.1 全排列 ​

  • 用 used 布尔数组标记已选元素；每层在未用元素里选一个。
python
def permute(nums):
    res, n = [], len(nums)
    used = [False] * n
    def dfs(path):
        if len(path) == n:
            res.append(path[:]); return
        for i in range(n):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            dfs(path)
            path.pop()
            used[i] = False
    dfs([])
    return res
def permute(nums):
    res, n = [], len(nums)
    used = [False] * n
    def dfs(path):
        if len(path) == n:
            res.append(path[:]); return
        for i in range(n):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            dfs(path)
            path.pop()
            used[i] = False
    dfs([])
    return res

9.2 组合 / 组合总和 ​

  • 组合用"起点下标"避免回头（for i in range(start, n)），保证不重复、顺序无关。
  • 组合总和 II（元素可重且每个只能用一次）：先排序，同一层跳过与上一个相同的元素。

9.3 子集 ​

  • 每个元素"选/不选"两个分支；或按起点枚举长度。模板与组合几乎一致。

9.4 N 皇后 ​

  • 逐行放皇后，用三个集合记录"列、主对角线、副对角线"是否被占。
  • 主对角线特征 row - col 恒定，副对角线 row + col 恒定 → O(1) 判冲突。
  • 时间 O(n!)，剪枝后实际远小于；空间 O(n)。

9.5 去重套路总结 ​

场景手段
排列中元素位置去重（含重复元素的全排列）used + 同层 if i>0 and nums[i]==nums[i-1] and not used[i-1]: continue
组合中避免同一值同层重复选排序 + 同层跳过 nums[i] == nums[i-1]
防止顺序无关的重复路径用 start 起点约束不回头
收集结果类型子集/排列类题目注意 path[:] 深拷贝

十、贪心 vs DP ​

10.1 贪心的适用 ​

  • 贪心：每一步做当前看起来最优的局部选择，期望得到全局最优。
  • 能用贪心的题有"贪心选择性质"（局部最优即全局最优），如：区间调度（按结束时间排序）、找零（硬币面额成倍数关系）、跳跃游戏、加油站。
  • 贪心通常 O(n log n)（排序占大头），比 DP 快，但证明难、容易错。

10.2 对比表 ​

维度贪心动态规划
决策方式只看当前局部最优考察所有子问题并取最优
是否需要"后悔"不需要需要（保留多个候选）
正确性证明必须（贪心选择性质+最优子结构）转移方程正确即可
复杂度常 O(n log n)常 O(n²) 或更高
典型区间调度、Huffman背包、编辑距离

10.3 常见"伪贪心"陷阱 ​

  • 0-1 背包不能用"单位价值从高到低"贪（容量碎片会浪费）；必须 DP。
  • 找零 [1,3,4] 凑 6：贪心 4+1+1=3 枚，最优 3+3=2 枚 → 面额不成倍数时贪心失效。
  • 面试建议：能证明就贪心；证不了但有明显子结构就上 DP，先保证正确再谈优化。

Copyright © 2024-present xiaocao