算法►动态规划

线性 DP：字符串问题

本文通过 1143、72、583 三道典型题目，总结出线性 DP 的核心不在于「一维还是二维」，而在于当前状态只依赖于“更小规模的历史状态”，并且状态推进顺序是线性的；字符串 DP 与背包 DP 在模型上是统一的，只是状态含义不同。

一、什么是「线性 DP」——不是维度，而是递推方向

最初我把“线性 DP”理解为一维数组，但这其实是结果，不是本质。

1. 状态只依赖于“过去”

  • dp[i] 或 dp[i][j] 只从更小的 i / j 推导
  • 不存在回头依赖、环形依赖

2. 状态推进顺序是线性的

  • 一维：i = 1 → n
  • 二维：固定一个维度，另一个维度线性推进
    （例如先枚举 i，再枚举 j）

3. 可以被空间优化（但不是必须）

  • 如果 dp[i] 只依赖 dp[i-1]，就能压缩
  • 如果 dp[i][j] 只依赖上一行或左侧，也可以压缩

是否能压缩 ≠ 是否是线性 DP

二、统一视角：字符串 DP 与背包 DP 本质相同

维度 背包问题 字符串问题
输入 数组 字符串
状态含义 前 i 个物品 前 i / j 个字符
决策 选 / 不选 保留 / 删除 / 替换
本质 枚举当前位置的决策 枚举当前位置的操作

01 背包、完全背包、LCS、编辑距离，本质上都是“位置 + 决策”的线性 DP。

三、经典模型一：1143 最长公共子序列（LCS）

状态定义

dp[i][j]：
word1 前 i 个字符 与 word2 前 j 个字符 的最长公共子序列长度

注意：

  • 是「前 i 个」，不是「第 i 个」
  • 这是为了让 dp[0][*] 成为合法边界

决策拆解（从 DFS 到 DP）

站在回溯角度：

  • 当前考察 word1[i-1] 和 word2[j-1]
  • 两种情况：
    • 相等 → 一起加入子序列
    • 不等 → 放弃其中一个

状态转移（核心）

1
2
3
4
if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

这是一个非常“干净”的线性 DP：

  • 依赖方向：左、上、左上
  • 遍历顺序：i 从小到大，j 从小到大

四、经典模型二：72 编辑距离（Edit Distance）

状态定义

dp[i][j]：
word1 前 i 个字符 转换为 word2 前 j 个字符 的最少操作数

为什么它和 LCS 是同一类问题？

可以从“操作视角”统一理解：

操作 对应状态变化
删除 word1[i-1] dp[i-1][j] + 1
插入的字符与 word2[j] 相同，所以递归到 word2[j-1] dp[i][j-1] + 1
替换 / 保留 dp[i-1][j-1] + cost

其中：

  • cost = 0（字符相等）
  • cost = 1（字符不等）

状态转移方程

1
2
3
4
5
6
7
8
if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = min(
        dp[i-1][j],     // 删除
        dp[i][j-1],     // 插入
        dp[i-1][j-1]    // 替换
    ) + 1

和 LCS 的区别不在于 DP 框架，而在于：

  • 相等时是否“奖励 +1”
  • 不等时是取 max 还是 min

五、模型变形：583 两个字符串的删除操作

这道题是 编辑距离的特例：

  • 只能删除
  • 允许对两个字符串都删除

两种等价解法（体现思维深度）

解法一：直接 DP（编辑距离删减版）

  • 只保留「删除」相关转移
  • 不允许插入和替换

解法二：LCS 转化（更优雅）

1
2
最少删除次数 =
    len(word1) + len(word2) - 2 * LCS(word1, word2)

六、字符串 DP vs 背包 DP：本质对比总结

维度 背包 字符串 DP
状态 dp[i][j] dp[i][j]
i 的含义 前 i 个物品 前 i 个字符
j 的含义 容量 / 价值 另一个字符串长度
决策 选 / 不选 删除 / 插入 / 替换
共同点 线性推进、局部最优构成全局最优

七、总结

  • 线性 DP 的核心是 “状态规模单调变小 + 线性遍历顺序”
  • LCS、编辑距离、字符串删除问题 本质是一套 DP 模型
  • 能从 DFS → 状态定义 → 转移方程 → 空间优化，是完整 DP 能力的体现
  • 理解状态含义，比记公式重要得多

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。