引言 (Introduction)
上一篇我们从理论到实践建立了一维 DP 的建模框架。但面对一个二维网格（Grid），状态不再只是「考虑第 $i$ 个元素」那么简单——你需要同时描述行和列两个维度。
本文是本系列第二篇，聚焦于二维 DP 的建模范式。我们将通过三道经典题目（不同路径 62、最小路径和 64、最大正方形 221），掌握从一维到二维的建模迁移，以及「从 DP 表中反推最优路径」这个容易被忽略的实用技巧。
1. 从一维到二维：状态表格的建模
1.1 什么时候需要二维状态？
一个直观的判断法则：如果输入是二维结构（矩阵、网格），且问题要求保留两个维度的位置信息，则至少需要二维状态。
一维 DP 的状态通常是 $dp[i]$，对应「前 $i$ 个元素」。二维 DP 的状态通常是 $dp[i][j]$，对应「位置 $(i, j)$」或「考虑前 $i$ 行、前 $j$ 列」。
1.2 转移方向的多样性
在一维 DP 中，转移方向通常是单向的（从左到右）。在二维 DP 中，一个格子可以从上、左、左上等多个方向转移而来：
(i-1, j-1) (i-1, j)
\ |
\ ↓
(i, j-1) → (i, j)
这并不意味着我们要处理三个方向——具体使用哪些方向取决于题目的转移方程。但原则上，二维 DP 的填表顺序必须保证被依赖的状态已经计算出。
1.3 空间优化的通用套路
一维 DP 可以把 $O(n)$ 空间优化为 $O(1)$（滚动变量）。二维 DP 可以把 $O(mn)$ 空间优化为 $O(n)$（滚动数组）——只保留当前行和上一行。
对于只依赖上一行和当前行左侧的转移（如路径类问题），一维滚动数组足以胜任。
2. LeetCode 62：不同路径
题目：$m \times n$ 网格，从左上角出发，每次只能向右或向下移动，到达右下角有多少条不同路径？
2.1 状态定义与转移
$dp[i][j]$：从 $(0, 0)$ 到达 $(i, j)$ 的路径数。
转移方程：
$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$即到达 $(i, j)$ 的路径 = 从上方走来的路径数 + 从左侧走来的路径数。
边界：第一行和第一列的格子都只有 1 条路径（一直向右或一直向下）。
2.2 完整代码
from typing import List
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 空间优化：只用一维数组
dp: List[int] = [1] * n # 第一行全为 1
for i in range(1, m):
for j in range(1, n):
dp[j] = dp[j] + dp[j - 1] # dp[j] 来自上一行，dp[j-1] 来自当前行左侧
return dp[-1]
复杂度：时间 $O(mn)$，空间 $O(n)$。
2.3 为什么一维数组就够了？
填表时 $dp[j]$ 的旧值是上一行同列的值，$dp[j-1]$ 已更新为当前行左侧的值。二维的 dp[i][j] = dp[i-1][j] + dp[i][j-1] 在一维中恰好对应 dp[j] = dp[j] + dp[j-1]。
滚动数组的诀窍：先确认转移只依赖「上一行 + 本行之前位置」，然后改内层循环的方向。如果依赖的是上一行和本行之后的位置（如从右下往左上填），循环方向也要相应反转。
3. LeetCode 64：最小路径和
题目：$m \times n$ 网格，每个格子有一个非负整数。从左上到右下（只能向右或向下），求路径上数字之和的最小值。
3.1 状态转移
$dp[i][j]$：到达 $(i, j)$ 的最小路径和。
$$dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j]$$即在「从上方来」和「从左侧来」之间选择代价更小的。
边界：$dp[0][0] = grid[0][0]$。第一行只能从左侧来，第一列只能从上方来。
3.2 完整代码
from typing import List
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp: List[int] = [0] * n
dp[0] = grid[0][0]
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j] # 第一行初始化
for i in range(1, m):
dp[0] += grid[i][0] # 每行第一列
for j in range(1, n):
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
return dp[-1]
复杂度：时间 $O(mn)$，空间 $O(n)$。
3.3 从 DP 表反推最优路径
DP 不仅给出最优值，还能重建最优解本身。这在很多工程场景（如导航、对齐）中至关重要。
from typing import List, Tuple
def reconstruct_path(grid: List[List[int]]) -> List[Tuple[int, int]]:
"""从 DP 表中反推一条最优路径"""
m, n = len(grid), len(grid[0])
# 先用二维 DP 填满整个表
dp: List[List[int]] = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n):
dp[0][j] = dp[0][j - 1] + grid[0][j]
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for j in range(1, n):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
# 从右下角回溯到左上角
path: List[Tuple[int, int]] = []
i, j = m - 1, n - 1
while i > 0 or j > 0:
path.append((i, j))
if i == 0:
j -= 1
elif j == 0:
i -= 1
elif dp[i - 1][j] < dp[i][j - 1]:
i -= 1
else:
j -= 1
path.append((0, 0))
path.reverse()
return path
回溯逻辑：从终点出发，每一步看哪个邻居 $dp$ 值更小，就往哪边走。这等价于沿着转移方程逆向追溯。
4. LeetCode 221：最大正方形
题目：$m \times n$ 的 '0'/'1' 矩阵，找出只包含 '1' 的最大正方形的面积。
4.1 状态定义
$dp[i][j]$：以 $(i, j)$ 为右下角的最大正方形边长。
转移方程：
$$dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 \quad (\text{if } matrix[i][j] = '1')$$直觉解释：以 $(i, j)$ 为右下角的正方形，其大小受限于三个相邻位置的正方形大小——左边、上边、左上。取三者的最小值再加 1，保证四方都是 '1'。
dp[i-1][j-1] dp[i-1][j]
↓ ↓
dp[ i ][j-1] → dp[ i ][j]
4.2 完整代码
from typing import List
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
dp: List[int] = [0] * (n + 1) # 多一列作为哨兵
max_side = 0
prev = 0 # 保存左上角 dp[i-1][j-1]
for i in range(m):
for j in range(n):
temp = dp[j + 1] # 旧值 = dp[i-1][j]，下一轮的左上角
if matrix[i][j] == '1':
dp[j + 1] = min(dp[j + 1], dp[j], prev) + 1
max_side = max(max_side, dp[j + 1])
else:
dp[j + 1] = 0
prev = temp
return max_side * max_side
复杂度：时间 $O(mn)$，空间 $O(n)$。
哨兵技巧：dp 数组多开一列（$n+1$），让 $dp[0]$ 恒为 0，省去对 $j=0$ 的特殊判断。prev 变量保存 $(i-1, j-1)$ 的值（因为在滚动数组中它会被覆盖）。
5. 二维 DP 的建模框架
回顾三道题的转移依赖关系：
| 题目 | 状态定义 | 依赖方向 | 空间优化 |
|---|---|---|---|
| 62 不同路径 | 到达 $(i,j)$ 的路径数 | 上 + 左 | 一维数组，正序 |
| 64 最小路径和 | 到达 $(i,j)$ 的最小代价 | 上 + 左取 min | 一维数组，正序 |
| 221 最大正方形 | 以 $(i,j)$ 为右下角的最大边长 | 上 + 左 + 左上取 min | 一维数组 + prev |
统一的二维 DP 建模流程：
- 如果输入是网格/矩阵，$dp[i][j]$ 几乎总是表示「与位置 $(i, j)$ 相关的」某种最值/计数。
- 画一个 $3 \times 3$ 的小表格，手工推导转移关系。
- 确定填表顺序：行优先（外循环 $i$，内循环 $j$）还是列优先？依赖左上角的要特别注意循环方向。
- 空间优化：滚动数组保留上一行信息，如果还需要左上角，额外用一个变量保存。
结论 (Conclusion)
本文完成了 DP 从一维到二维的跃迁。核心收获：
- 二维 DP 的 $dp[i][j]$ 同时保留行和列的信息，依赖方向通常来自上方、左侧或左上。
- 滚动数组可以将空间从 $O(mn)$ 优化到 $O(n)$，但需要额外关注被覆盖的值（如左上角）。
- 最优解不仅包含数值，还能从 DP 表中反向回溯出完整的路径。
下一篇预览：背包问题族——这是 DP 最具代表性的应用领域。我们将学习 0/1 背包、完全背包的空间优化技巧，以及「组合数」vs「排列数」在循环顺序上的微妙差异（LeetCode 416、322、518）。