[!info] related notes 算法面试题型 MOC 动态规划 最长公共子序列 编辑距离 不同路径 最小路径和

网格 DP 与双序列 DP

一句话

这类题的状态大多长这样：dp[i][j]，表示走到某个坐标、或者处理到两个前缀时的答案。

一页式速查表

小类	常见状态	转移关键词	入门题	进阶题
网格路径计数	dp[i][j]	上 + 左	[[unique-paths	不同路径]]
网格最优值	dp[i][j]	min/max(上, 左)	[[minimum-path-sum	最小路径和]]
双序列最值	dp[i][j]	左 / 上 / 左上	[[longest-common-subsequence	LCS]]、[[edit-distance
双序列方案数	dp[i][j]	选 / 不选当前字符	[[distinct-subsequences	不同的子序列]]

识别信号

• 棋盘 / 网格 / 矩阵
• 从上、左、左上转移
• 两个字符串 / 两个数组的前缀比较

1. 网格 DP

常见状态

dp[i][j] = 从起点到 (i, j) 的方案数 / 最优值

常见转移

• 从上面来：dp[i - 1][j]
• 从左边来：dp[i][j - 1]

样例：不同路径

题意：机器人每次只能向右或向下，问到右下角的路径数。

转移：

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

边界：第一行和第一列都只有 1 种走法。

样例：最小路径和

题意：每次向右或向下，求路径数字和最小值。

转移：

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

2. 双序列 DP

常见状态

dp[i][j] = s 的前 i 个字符和 t 的前 j 个字符的答案

样例：最长公共子序列（LCS）

题目：最长公共子序列

转移

• 如果 s[i - 1] === t[j - 1]：

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

• 否则：

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

含义理解

它是典型的“前 i 个元素”状态，不是“以 i 结尾”。

样例：编辑距离

题目：编辑距离

状态

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

转移

• 插入
• 删除
• 替换 / 不替换

如果最后一个字符相同：

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

否则：

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

高频坑

• 下标和前缀长度混了：i 表示长度时，访问字符通常是 s[i - 1]
• 第一行 / 第一列初始化漏掉
• 网格题忘了先处理边界，直接访问 dp[-1][j]

模板与代表题

• 模板：LCS 模板、编辑距离模板
• 网格题：不同路径、最小路径和
• 双序列题：最长公共子序列、编辑距离
• 方案数进阶：不同的子序列