网格动态规划 (2D DP)：掌握二维动态规划

什么是网格动态规划？

网格DP（二维动态规划） 是一种状态定义在二维网格或矩阵上的模式。DP表是一个二维数组，其中 dp[i][j] 表示位置 (i, j) 处子问题的最优解。

核心特征

1. 二维状态: dp[i][j] 表示单元格 (i, j) 处的某个最优值
2. 空间依赖: 每个单元格依赖于相邻单元格（上方、左方、对角线）
3. 逐行迭代: 我们通常逐行、从左到右填充表格
4. 常见时间复杂度: $O(m \times n)$

两大主要类别

类别	描述	示例
路径问题	在网格中计数/优化路径	不同路径、最小路径和
字符串DP	使用二维表比较两个序列	编辑距离、LCS

---

网格路径问题

直观理解

不同路径：计算从左上角到右下角的路径数
          （只能向右或向下移动）

     0   1   2   3
   ┌───┬───┬───┬───┐
 0 │ 1 │ 1 │ 1 │ 1 │  ← 第一行：只有1种方式（全部向右）
   ├───┼───┼───┼───┤
 1 │ 1 │ 2 │ 3 │ 4 │
   ├───┼───┼───┼───┤
 2 │ 1 │ 3 │ 6 │10 │  → 答案 = 10
   └───┴───┴───┴───┘
     ↑
     第一列：只有1种方式（全部向下）

dp[i][j] = dp[i-1][j] + dp[i][j-1]
           （从上方）  +  （从左方）

---

交互式可视化：不同路径

Loading visualization...

---

问题一：不同路径 (LC 62)

问题：计算从左上角到右下角的不同路径数。只能向右或向下移动。

状态定义: dp[i][j] = 到达单元格 (i, j) 的不同路径数

转移方程:

dp[i][j] = dp[i-1][j] + dp[i][j-1]
           （从上方）  +  （从左方）

基础情况: 第一行和第一列都是1（只有一种方式到达它们）

JavaPythonJavaScript

Loading...

数学解法

这个问题等价于在 (m-1+n-1) 次移动中选择哪些是”向下”：

$\binom{m+n-2}{m-1} = \frac{(m+n-2)!}{(m-1)!(n-1)!}$

---

问题二：不同路径 II (LC 63)

问题：与不同路径相同，但有障碍物（标记为1）。

关键修改: 如果单元格是障碍物，dp[i][j] = 0

JavaPythonJavaScript

Loading...

关键洞察

障碍物阻断路径。一旦在第一行/列遇到障碍物，该方向之后的所有单元格都无法从该方向到达。

---

交互式可视化：最小路径和

Loading visualization...

---

问题三：最小路径和 (LC 64)

问题：找到从左上角到右下角的最小路径和。只能向右或向下移动。

状态定义: dp[i][j] = 到达单元格 (i, j) 的最小路径和

转移方程:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
           （从上方，     从左方）   +  当前单元格值

JavaPythonJavaScript

Loading...

---

交互式可视化：最大正方形

Loading visualization...

---

问题四：最大正方形 (LC 221)

问题：找到只包含1的最大正方形，返回其面积。

状态定义: dp[i][j] = 以 (i, j) 为右下角的最大正方形的边长

转移方程:

if matrix[i][j] == '1':
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
               （上方，       左方，       对角线）

关键洞察：为什么取min()？

正方形大小受最小邻居的限制：

情况：dp[i-1][j]=3, dp[i][j-1]=2, dp[i-1][j-1]=2

   ┌───┬───┬───┬───┐
   │   │   │   │   │   即使上方有3×3的正方形，
   ├───┼───┼───┼───┤   左方和对角线只有2×2。
   │   │   │ 2 │ 3 │   
   ├───┼───┼───┼───┤   在 (i,j) 处，我们只能形成3×3
   │   │   │ 2 │ ? │   的正方形，前提是所有三个邻居
   └───┴───┴───┴───┘   都支持它。

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

JavaPythonJavaScript

Loading...

---

字符串DP（二维模式）

字符串DP使用二维表，其中 dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的答案。

直观理解：编辑距离

将 "horse" 转换为 "ros"

         ""  r   o   s
      ┌───┬───┬───┬───┐
   "" │ 0 │ 1 │ 2 │ 3 │  ← 插入 r, o, s
      ├───┼───┼───┼───┤
    h │ 1 │ 1 │ 2 │ 3 │  ← h≠r: 替换(0+1), 删除(1+1), 插入(1+1)
      ├───┼───┼───┼───┤
    o │ 2 │ 2 │ 1 │ 2 │  ← o=o: 不需要操作，取对角线
      ├───┼───┼───┼───┤
    r │ 3 │ 2 │ 2 │ 2 │  ← r=r: 不需要操作，取对角线
      ├───┼───┼───┼───┤
    s │ 4 │ 3 │ 3 │ 2 │  ← s=s: 不需要操作
      ├───┼───┼───┼───┤
    e │ 5 │ 4 │ 4 │ 3 │  → 答案：3次操作
      └───┴───┴───┴───┘

---

问题五：编辑距离 (LC 72)

问题：找到将word1转换为word2所需的最少操作数（插入、删除、替换）。

状态定义: dp[i][j] = 将word1[0..i-1]转换为word2[0..j-1]的最少操作数

转移方程:

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]      // 不需要操作
else:
    dp[i][j] = 1 + min(
        dp[i-1][j-1],  // 将word1[i-1]替换为word2[j-1]
        dp[i-1][j],    // 删除word1[i-1]
        dp[i][j-1]     // 插入word2[j-1]
    )

JavaPythonJavaScript

Loading...

理解各种操作

操作	在DP表中的移动	含义
替换	对角线 (i-1, j-1) → (i, j)	改变字符，两边都前进
删除	上方 (i-1, j) → (i, j)	从word1删除，word1前进
插入	左方 (i, j-1) → (i, j)	添加到word1，word2前进

---

问题六：最长公共子序列 (LC 1143)

问题：找到两个字符串的最长公共子序列的长度。

状态定义: dp[i][j] = text1[0..i-1]和text2[0..j-1]的LCS长度

转移方程:

if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1   // 包含这个字符
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  // 跳过一个字符

JavaPythonJavaScript

Loading...

---

空间优化技巧

网格DP通常可以从 $O(m \times n)$ 优化到 $O(n)$ 或 $O(\min(m, n))$ 空间。

逐行优化

由于我们只需要前一行，可以使用单个一维数组：

// 优化前：O(m*n) 空间
int[][] dp = new int[m][n];
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}

// 优化后：O(n) 空间
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j] + dp[j-1];
        //      ↑ 上方（前一行的dp[j]）
        //             ↑ 左方（当前行的dp[j-1]）
    }
}

关键洞察

当我们从左到右处理时：

• dp[j]（更新前）= 前一行的值 = dp[i-1][j]
• dp[j-1]（更新后）= 当前行的值 = dp[i][j-1]

---

常见模式总结

问题类型	状态定义	转移方程	空间
路径计数	dp[i][j] = 到(i,j)的路径数	dp[i-1][j] + dp[i][j-1]	O(n)
路径优化	dp[i][j] = 到(i,j)的最小/最大值	opt(dp[i-1][j], dp[i][j-1]) + val	O(n)
正方形查找	dp[i][j] = (i,j)处的边长	min(3个邻居) + 1	O(n)
字符串匹配	dp[i][j] = s1[0..i], s2[0..j]的答案	取决于字符匹配	O(n)

---

迭代顺序

对于大多数网格DP问题，我们逐行、从左到右迭代：

for i from 0 to m-1:
    for j from 0 to n-1:
        compute dp[i][j]

这确保了 dp[i-1][j] 和 dp[i][j-1] 在 dp[i][j] 之前被计算。

例外：对角线填充

某些问题（如区间DP）需要对角线迭代：

for length from 1 to n:
    for i from 0 to n-length:
        j = i + length - 1
        compute dp[i][j]

---

面试技巧

如何识别网格DP

1. 网格中的路径 → 网格路径DP
2. 比较两个字符串 → 字符串DP（二维表）
3. 找具有某属性的子矩阵 → 考虑将 dp[i][j] 作为右下角

常见错误

1. 基础情况错误: 记住第一行和第一列通常需要特殊处理
2. 索引混淆: 注意 dp[i][j] 是表示”前i个”还是”索引i”
3. 忘记障碍物: 对于被阻挡的单元格设置 dp[i][j] = 0

优化问题

1. “能减少空间吗？” → 使用一维数组（行优化）
2. “如果网格很大怎么办？” → 流式处理，如果适用
3. “能重建路径吗？” → 从dp表回溯

---

练习题目

路径问题

• LC 62: 不同路径
• LC 63: 不同路径 II
• LC 64: 最小路径和
• LC 120: 三角形最小路径和
• LC 174: 地下城游戏

矩阵问题

• LC 221: 最大正方形
• LC 85: 最大矩形
• LC 764: 最大加号标志

字符串DP（二维）

• LC 72: 编辑距离
• LC 1143: 最长公共子序列
• LC 516: 最长回文子序列
• LC 115: 不同的子序列
• LC 10: 正则表达式匹配

---

总结

网格DP关键要点：

1. 状态是二维的: dp[i][j] 表示位置 (i, j) 处的最优值，或两个序列前缀的答案

2. 两大主要类别:

   • 路径问题: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
   • 字符串问题: dp[i][j] = f(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

3. 空间优化: 大多数2D DP可以通过逐行处理减少到O(n)

4. 迭代顺序: 逐行、从左到右确保满足依赖关系

5. 基础情况: 第一行和第一列通常需要特殊初始化

掌握这些模式，你就能解决面试中大多数网格DP问题！