多维动态规划（题单顺序）

• 状态：dp[i][j] 表示什么（一定要带上“含义 + 范围”）。
• 转移：dp[i][j] 从哪些更小状态来，为什么不会漏/重。
• 初始化：边界（第一行/第一列/空串/长度为 0）怎么设，避免越界。
• 遍历顺序：保证用到的状态已经算好（常见是从小到大）。
• 优化：能否滚动数组（把二维压成一维），以及滚动时更新方向是否会污染数据。

• 题意：你站在左上角，每次只能往右或往下走一步，问到右下角一共有多少种不同的走法？
• 核心想法：走到某一个格子时，你只能从它的上面一格下来，或者从它的左边一格过来，没有别的路。所以「到达这个格子的走法数」=「到达上面那格的走法数」+「到达左边那格的走法数」。写成式子就是：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
• 边界：第一行只能一直往右走，第一列只能一直往下走，所以第一行、第一列每个格子都只有 1 种走法，初始化为 1。
• 空间优化：算每一行时只用得到「上一行」的结果，所以可以用一维数组「滚动」：dp[j] 表示当前行第 j 列有多少种走法，更新时用「上一行的 dp[j]」加上「当前行左边的 dp[j-1]」，即 dp[j] = dp[j] + dp[j-1]。

思路相同：当前格子的值只依赖「上面」和「左边」，转移时用一维滚动即可，例如：

dp[j] = dp[j] + dp[j-1]

• 和 62 一样，只是把“路径条数”换成“路径代价最小”。
• 到 grid[i][j] 的最小代价只能来自上或左的最小代价，再加上当前格子权重。
• 一维滚动时：
  • dp[j] 表示从上方来的最小和
  • dp[j-1] 表示从左方来的最小和（因为已更新到当前行）
  • 所以 dp[j] = min(dp[j], dp[j-1]) + grid[i][j]。

• 回文的定义：左右对称。
• 关键推理：最长回文一定有一个“中心”：
  • 奇数长度回文中心是一个字符（比如 aba 的中心是 b）
  • 偶数长度回文中心在两个字符之间（比如 abba 的中心在 bb 之间）
• 所以我们枚举每个可能中心，然后向两边扩展，直到不再相等。
• 为什么是 (O(n^2))：中心有 (O(n)) 个，每次扩展最坏 (O(n))。
• 这题也可以用二维 DP 表 pal[i][j]，同样是 (O(n^2))，中心扩展更省空间、更直观。

题目在问什么？

想象有两排字母，顺序固定。你从第一排里挑几个、从第二排里也挑几个，要挑出一模一样的一串（顺序一致）。问：这串最长能有多长？

例："abcde" 和 "ace"，能挑出 "ace"，长度 3。

推理的起点：先解决“小一点”的问题

如果只让你看两串的前几格，你也会算“这两小段里最长公共串多长”。我们就把这个答案记在一张表里：dp[i][j] = text1 前 i 个 与 text2 前 j 个 的最长公共子序列长度。

表从左到右、从上到下填。填到 (i, j) 时，左边、上边、左上的格子都早就填好了，我们只要想：多出来的这两个字符（text1 的第 i 个 和 text2 的第 j 个）该怎么用？

情况一：这两个字符刚好相同

那就太好了：它们可以一起配对，算进公共串里。
“前面的部分”我们早就算过了，就是左上角那一格 dp[i-1][j-1]。所以当前格 = 左上 + 1：

• dp[i][j] = dp[i-1][j-1] + 1

（就像两个人最后一位对上号了，长度自然多 1。）

情况二：这两个字符不一样

公共子序列的意思是：从两串里挑出同一串，也就是两边的字符要能一一配对（相同的才能配）。现在最后这两个字符不同，配不成一对，所以没法把“这两个”同时都算进公共串里。

那我们只能选一种「放弃」方式：要么放弃 text1 的最后这个（相当于只考虑 text1 前 i-1 个 和 text2 前 j 个），答案在上面那格 dp[i-1][j]；要么放弃 text2 的最后这个（只考虑 text1 前 i 个 和 text2 前 j-1 个），答案在左边那格 dp[i][j-1]。我们要的是最长公共串，所以取这两种里更大的：

• dp[i][j] = max(上面, 左边) = max(dp[i-1][j], dp[i][j-1])

小结

• 最后一位相同 → 左上 +1（配对成功）。
• 最后一位不同 → 上面、左边取 max（只能丢掉其中一串的最后一位，选更优的那边）。

填完表，右下角 dp[m][n] 就是答案。

套路一样：看两串「末尾」是否相同，相同就对角 +1，不同就从上/左取最大：

if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])

这题是字符串 DP 里的另一座大山，但本质和 LCS 是亲兄弟。掌握它，你对「字符串怎么一点点变形」会理解得非常透。

题目在干嘛？

给你两个单词：word1 → 变成 → word2。每次只能做 3 种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

问：最少要几步？

例如 horse → ros 的一种做法：

• horse → rorse（替换 h→r）
• rorse → rose（删除 r）
• rose → ros（删除 e）
  答案 = 3。

核心思路（一句话）

把大问题拆成：前 i 个字符变成前 j 个字符要几步。

DP 定义

dp[i][j] = 把 word1 前 i 个字符 变成 word2 前 j 个字符 的最少操作数。

注意：是“前 i 个”，不是下标 i（所以 i、j 从 1 到 m、n，0 留给空串）。

初始化（边界）

状态转移（灵魂所在）

看最后一个字符：word1[i-1] 和 word2[j-1]。

情况 1：两个字符相同

那最后这个字符不用管，等于没变：dp[i][j] = dp[i-1][j-1]（前面怎么变，现在就怎么变）。

情况 2：字符不同

必须做一次操作（插入 / 删除 / 替换），取步数最少的一种：

为什么对应这个格子？

• dp[i-1][j] + 1（删除）：当前是“word1 前 i 个”对“word2 前 j 个”。若删掉 word1 的最后一个，剩下的问题就是“word1 前 i-1 个 → word2 前 j 个”，答案已经算在 dp[i-1][j] 里，再加这一次删除就是 dp[i-1][j] + 1。
• dp[i][j-1] + 1（插入）：若在 word1 末尾插入 word2[j-1]，插入后末尾已经对齐；等价于先解决“word1 前 i 个 → word2 前 j-1 个”（dp[i][j-1]），再用 1 步插入补上 word2 的最后一个。
• dp[i-1][j-1] + 1（替换）：若把 word1[i-1] 替换成 word2[j-1]，两边末尾就一样了；等价于先解决“word1 前 i-1 个 → word2 前 j-1 个”（dp[i-1][j-1]），再加这 1 次替换。

取最小：dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

过程直观理解

可以理解为：从左上角走到右下角，每一步都在做「最省操作的选择」。代码见上方最优解。

复杂度：时间 O(m×n)，空间 O(m×n)（可优化到 O(n)）。

和 LCS 的关系

LCS 是「尽量不改」，编辑距离是「最少改几步」，本质都是在比较两个字符串的对齐方式。

最通俗总结

• 字符一样 → 继承左上角。
• 字符不一样 → 从「替换、删除、插入」里选最便宜的一步。

延伸：若只允许插入和删除（不允许替换），有结论：编辑距离 = len1 + len2 − 2×LCS，能把两道题直接打通。