一、DP 的两个前提

动态规划 = 递归 + 记住已经算过的答案。 就这么简单，但要用对需要两个条件：

条件 含义 缺了会怎样
① 最优子结构 问题的最优解包含子问题的最优解 无法通过组合子问题的解得到答案
② 重叠子问题 递归会反复求解同一个子问题 没有重叠就是分治（第 28 讲），记忆化没有收益

一个直观的对照

朴素递归求斐波那契：

              F(5)
           ╱        ╲
       F(4)          F(3)         ← F(3) 出现 2 次
      ╱    ╲        ╱    ╲
   F(3)    F(2)  F(2)    F(1)     ← F(2) 出现 3 次
   ╱  ╲    ╱  ╲   ╱ ╲
 F(2) F(1) …            共 Θ(φⁿ) 个节点

只有 n 个不同的子问题，却算了指数次。 记住每个答案，复杂度立刻从 Θ(φⁿ) 降到 Θ(n)。

⭐ DP 的本质是「用空间换掉重复计算」。所以 DP 的复杂度总是：

时间 = 状态数 × 每个状态的转移代价
空间 = 状态数（常可优化）

这个公式是分析和设计 DP 的唯一工具。

二、两种实现方式

自顶向下：记忆化搜索

func fibMemo(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    v := fibMemo(n-1, memo) + fibMemo(n-2, memo)
    memo[n] = v
    return v
}

自底向上：递推填表

func fibDP(n int) int {
    if n <= 1 { return n }
    prev, cur := 0, 1
    for i := 2; i <= n; i++ {
        prev, cur = cur, prev+cur // 滚动变量，空间 O(1)
    }
    return cur
}
记忆化（自顶向下） 递推（自底向上）
写法 贴近递归定义，容易写对 需要想清楚填表顺序
只算需要的状态 ✓ ✗ 全部计算
常数因子 大（递归 + map/哈希开销） 小（数组顺序访问，缓存友好）
空间优化（滚动数组） 难 容易
栈溢出风险 ✓ 深递归 无

⭐ 建议的工作流程：先写记忆化把逻辑想对，再改写成递推做优化。 直接写递推容易在填表顺序上出错。

三、设计 DP 的五步法

① 定义状态：dp[i][j] 表示什么？        ← 最难、最关键的一步
② 写出转移方程：dp 由哪些更小的状态得来？
③ 确定边界条件：最小的状态是什么？
④ 确定计算顺序：保证转移时依赖的状态已算好
⑤ 确定答案位置：从哪个状态读出最终答案？

⚠️ 95% 的 DP 困难出在第 ①步。 状态定义得不好，转移方程就写不出来，或者写出来是错的。

⭐ 状态定义的常见套路：

套路 形式 例子
前缀/后缀 dp[i] = 前 i 个元素的答案 LIS、爬楼梯
两个序列 dp[i][j] = A 前 i 个与 B 前 j 个 LCS、编辑距离
区间 dp[i][j] = 区间 [i,j] 的答案 矩阵链乘、石子合并
带资源约束 dp[i][w] = 前 i 个物品、容量 w 背包
带状态标志 dp[i][0/1] = 第 i 个选/不选 打家劫舍、股票买卖
树形 dp[u][…] = 以 u 为根的子树 树上最大独立集

四、最长公共子序列（LCS）

问题：两个序列 X、Y，求最长的公共子序列（可不连续，但保持相对顺序）。

① 状态：dp[i][j] = X 前 i 个字符与 Y 前 j 个字符的 LCS 长度。

② 转移：

            ┌ 0                                   i=0 或 j=0
dp[i][j] =  ┤ dp[i−1][j−1] + 1                    X[i−1] == Y[j−1]
            └ max(dp[i−1][j], dp[i][j−1])         否则

为什么？ 若末尾字符相同，它一定可以出现在某个最优 LCS 里（交换论证）；否则至少要放弃其中一个末尾字符。

func LCS(x, y string) int {
    m, n := len(x), len(y)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if x[i-1] == y[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]
}

        ""  A   B   C   B   D   A   B
    ""   0   0   0   0   0   0   0   0
    B    0   0   1   1   1   1   1   1
    D    0   0   1   1   1   2   2   2
    C    0   0   1   2   2   2   2   2
    A    0   1   1   2   2   2   3   3
    B    0   1   2   2   3   3   3   4    ⟵ LCS 长度 = 4（BCBA）

复杂度：状态数 Θ(mn)，每个转移 O(1) ⟹ Θ(mn) 时间，Θ(mn) 空间。

空间优化：滚动数组

dp[i][*] 只依赖 dp[i−1][*]，所以只保留两行：

func LCSLength(x, y string) int {
    prev := make([]int, len(y)+1)
    cur := make([]int, len(y)+1)
    for i := 1; i <= len(x); i++ {
        for j := 1; j <= len(y); j++ {
            if x[i-1] == y[j-1] {
                cur[j] = prev[j-1] + 1
            } else {
                cur[j] = max(prev[j], cur[j-1])
            }
        }
        prev, cur = cur, prev
    }
    return prev[len(y)]
}

空间降到 Θ(n)。

⚠️ 代价：无法回溯出具体的 LCS 序列，只能得到长度。要同时做到"线性空间 + 能输出序列"，需要 Hirschberg 算法（分治 + LCS，Θ(mn) 时间、Θ(min(m,n)) 空间）——diff 工具用的就是它。

应用：diff、git diff、生物序列比对、抄袭检测、版本合并。

五、编辑距离（Levenshtein）

问题：把字符串 A 变成 B，最少需要多少次操作（插入、删除、替换）。

① 状态：dp[i][j] = A 前 i 个字符变成 B 前 j 个字符的最少操作数。

② 转移：

            ┌ j                                        i = 0（全部插入）
            │ i                                        j = 0（全部删除）
dp[i][j] =  ┤ dp[i−1][j−1]                             A[i−1] == B[j−1]
            │ 1 + min( dp[i−1][j],      删除 A[i−1]
            └          dp[i][j−1],      插入 B[j−1]
                       dp[i−1][j−1] )   替换

func EditDistance(a, b string) int {
    m, n := len(a), len(b)
    prev := make([]int, n+1)
    cur := make([]int, n+1)
    for j := 0; j <= n; j++ { prev[j] = j }

    for i := 1; i <= m; i++ {
        cur[0] = i
        for j := 1; j <= n; j++ {
            if a[i-1] == b[j-1] {
                cur[j] = prev[j-1]
            } else {
                cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
            }
        }
        prev, cur = cur, prev
    }
    return prev[n]
}

Θ(mn) 时间，Θ(n) 空间。

⭐ 三个 min 项对应三种操作，这个对应关系必须记牢：

  • dp[i−1][j] → 删除 A 的第 i 个字符
  • dp[i][j−1] → 在 A 中插入 B 的第 j 个字符
  • dp[i−1][j−1] → 替换

应用：拼写检查、模糊搜索、DNA 比对、OCR 后处理、命令行的 “did you mean…"。

⚠️ 已被证明：在强指数时间假设（SETH）下，编辑距离不存在 O(n^{2−ε}) 的算法。所以 Θ(n²) 基本就是终点。

六、0-1 背包

问题：n 个物品，第 i 个重 wᵢ、价值 vᵢ。背包容量 W，每个物品最多取一次，求最大总价值。

① 状态：dp[i][w] = 只考虑前 i 个物品、容量为 w 时的最大价值。

② 转移：

dp[i][w] = max( dp[i−1][w],                        不取第 i 个
                dp[i−1][w−wᵢ] + vᵢ )               取第 i 个（w ≥ wᵢ 时）

func Knapsack01(weights, values []int, W int) int {
    dp := make([]int, W+1)
    for i := range weights {
        for w := W; w >= weights[i]; w-- { // ⭐ 必须倒序！
            dp[w] = max(dp[w], dp[w-weights[i]]+values[i])
        }
    }
    return dp[W]
}

⚠️ 为什么容量循环必须倒序

滚动数组把二维压成一维后，dp[w] 在被更新前存的是 dp[i−1][w]（上一行的值）。

倒序：更新 dp[w] 时，dp[w−wᵢ] 还没被本轮更新过 ⟹ 它是 dp[i−1][w−wᵢ]  ✓ 正确
正序：更新 dp[w] 时，dp[w−wᵢ] 已经被本轮更新 ⟹ 它是 dp[i][w−wᵢ]      ✗ 物品被重复取

⭐ 正序写法恰好就是「完全背包」（每个物品无限个）的正确写法！ 一个循环方向之差，解的是两个不同的问题：

func KnapsackComplete(weights, values []int, W int) int {
    dp := make([]int, W+1)
    for i := range weights {
        for w := weights[i]; w <= W; w++ { // 正序 ⟹ 可重复取
            dp[w] = max(dp[w], dp[w-weights[i]]+values[i])
        }
    }
    return dp[W]
}

⭐ 伪多项式时间

复杂度 Θ(nW)。这是多项式吗？

不是。 输入的编码长度是 Θ(n log W)（W 用二进制写只要 log W 位）。以输入长度衡量，Θ(nW) = Θ(n · 2^{log W}) 是指数级的。

n = 100，W = 10⁹  ⟹  nW = 10¹¹ 次操作，不可行
但输入长度只有  100 × 30 = 3000 比特

这种"关于数值是多项式，关于输入长度是指数"的复杂度叫伪多项式（pseudo-polynomial）时间。

⭐ 这一点非常重要：0-1 背包是 NP-完全问题（第 34 讲），Θ(nW) 的 DP 并没有"解决"它。当 W 很小时 DP 好用，W 很大时就必须转向近似算法或分支限界。

背包家族：

变体 关键差别
0-1 背包 容量倒序
完全背包（无限个） 容量正序
多重背包（每种 kᵢ 个） 二进制拆分成 O(log kᵢ) 个 0-1 物品
分组背包 每组只能选一个，组作为最外层循环
二维费用 再加一维 dp[w][v]

七、最长递增子序列（LIS）

O(n²) 的 DP

func LIS(a []int) int {
    dp := make([]int, len(a)) // dp[i] = 以 a[i] 结尾的 LIS 长度
    best := 0
    for i := range a {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if a[j] < a[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        best = max(best, dp[i])
    }
    return best
}

⭐ 注意状态定义：dp[i] 是”以 a[i] 结尾的 LIS"，而不是"前 i 个元素的 LIS"。后者无法转移——因为不知道前面的 LIS 以什么值结尾，无法判断 a[i] 能否接上去。

⭐ 这是一条重要的设计经验：当"前 i 个的答案"无法转移时，试试"以第 i 个结尾的答案"。 代价是最后要在所有 dp[i] 中取最大值。

⭐ O(n log n) 的贪心 + 二分

关键洞察：维护数组 tails，tails[k] = 长度为 k+1 的递增子序列中，结尾元素的最小可能值。

tails 必然是严格递增的，因此可以二分。

func LISFast(a []int) int {
    tails := []int{}
    for _, x := range a {
        // 找第一个 >= x 的位置（求最长严格递增用 >= ；非严格用 > ）
        i, _ := slices.BinarySearch(tails, x)
        if i == len(tails) {
            tails = append(tails, x) // x 比所有结尾都大，LIS 长度 +1
        } else {
            tails[i] = x // 用更小的 x 替换，为将来留下更多可能
        }
    }
    return len(tails)
}

⚠️ tails 数组本身不是一个合法的 LIS，它只是各长度的最优结尾值。要输出具体序列需要额外记录前驱。

⭐ “用更小的结尾替换"的直觉：长度不变但结尾更小，将来能接上的元素只多不少——这是一个贪心保持领先的论证（第 30 讲）。

推论（Dilworth 定理的应用）：把序列分成最少的非递增子序列，所需数量 = LIS 的长度。经典的"导弹拦截系统"问题就是这个。

八、更多经典 DP

问题 状态定义 复杂度
爬楼梯 / 斐波那契 dp[i] = 到第 i 阶的方案数 Θ(n)
打家劫舍 dp[i] = 前 i 家的最大收益 Θ(n)
零钱兑换（最少硬币） dp[v] = 凑出 v 的最少硬币 Θ(nV)
矩阵路径最小和 dp[i][j] = 到 (i,j) 的最小和 Θ(mn)
最大子数组（Kadane） dp[i] = 以 i 结尾的最大和 Θ(n)
回文子串判定 dp[i][j] = [i,j] 是否回文 Θ(n²)
股票买卖（含冷冻期/手续费/k 次） dp[i][状态] Θ(nk)

随堂自测

  1. DP 的两个前提是什么？缺少"重叠子问题"时该用什么方法？
  2. 写出"DP 复杂度 = ? × ?“这个公式，并用它分析 LCS。
  3. 记忆化和递推各有什么优劣？什么工作流程最稳妥？
  4. 设计 DP 的五步是什么？哪一步最容易出错？
  5. 写出 LCS 的转移方程并解释"末尾字符相同时为什么可以直接 +1”。
  6. LCS 用滚动数组优化到 Θ(n) 空间后，失去了什么能力？如何补救？
  7. 编辑距离的三个 min 项分别对应哪种操作？
  8. 0-1 背包的一维写法为什么必须倒序遍历容量？正序解的是什么问题？
  9. 什么是伪多项式时间？为什么 Θ(nW) 不算多项式？这对 0-1 背包意味着什么？
  10. LIS 的 DP 状态为什么定义成"以 a[i] 结尾"而不是"前 i 个”？
  11. 解释 O(n log n) LIS 中 tails 数组的含义，以及"用更小的值替换"为什么正确。