二维动态规划——像走棋盘一样找最优解

二维动态规划是一种在表格（网格）上一步步计算最优方案的方法。它把一个问题拆分成许多小格子，每个格子代表一个小问题的答案，然后按照一定的规则从左到右、从上到下填满整个表格，最终得到右下角那个最关键的答案。这种思路特别适合解决“只能向右或向下走”、“从起点到终点有多少种走法”或者“怎么走代价最小”这类问题。

什么是二维动态规划

想象你面前有一个m行n列的棋盘，你要从左上角走到右下角，每次只能向右或向下移动一格。那么，从起点到某个格子(i,j)有多少种不同的走法呢？这个问题就可以用二维动态规划来解决。

我们用一个二维表格 dp 来记录答案，其中 dp[i][j] 表示从起点 (0,0) 走到格子 (i,j) 的走法总数。因为只能向右或向下，所以走到 (i,j) 只能从它的左边 (i, j-1) 或者上边 (i-1, j) 过来。因此，dp[i][j] 的值就等于它左边格子的走法数加上上边格子的走法数。这个规律就是状态转移方程。

生活中的例子：用零花钱买零食

假设你每天有固定的零花钱（比如5元），你想买两种零食：薯片（2元/包）和巧克力（3元/块）。你一共有n天，每天可以决定买薯片、买巧克力、或者什么都不买，但要求不能超过当天的零花钱。问一共有多少种不同的购买方案？这其实就是一个二维动态规划：用行表示天数，列表示剩余零花钱，每个格子记录总方案数。不过，更经典的例子还是“网格寻路”。

小明上学的最短路径数（原有例子）

小明从家到学校，中间有障碍物，他想知道有多少条不同的最短路径。他只能向右或向下走。我们可以把每个路口看作一个格子，从起点到当前格子的路径数等于上方格子和左边格子的路径数之和（因为只能从这两个方向过来）。这就是一个典型的二维动态规划问题。

另一个例子：你和小伙伴排队买冰淇淋

你和好朋友一起去买冰淇淋，你排在第1个，他排在第1个（两排队伍）。每次只能让某一队前进一个人。问有多少种不同的排队顺序？这也可以看作网格问题：横坐标是你在队伍中的位置，纵坐标是朋友在队伍中的位置，每次只能向右（你前进）或向下（朋友前进）。计算方法一模一样。

关键概念拆解

1. 状态：什么是 `dp[i][j]`

在“网格寻路”中，dp[i][j] 表示从起点 (0,0) 走到格子 (i,j) 的路径总数。在“最小路径和”问题中，它可能表示走到这个格子的最小数字和。状态的设计要根据具体问题来决定，但核心是一样的：每个格子记录的是涉及该格子的小问题的答案。

2. 状态转移方程：如何填格子

我们已知 dp[i][j] 只依赖于它左边的格子 dp[i][j-1] 和上边的格子 dp[i-1][j]，所以转移方程是：

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

如果网格中有障碍物，则障碍物所在的格子路径数为0（不能走），并且从它出发的路径也要跳过。

def unique_paths(m, n):
    # 创建二维列表，全部初始化为0
    dp = [[0] * n for _ in range(m)]

    # 初始化第一行：只有向右一种走法
    for j in range(n):
        dp[0][j] = 1

    # 初始化第一列：只有向下一种走法
    for i in range(m):
        dp[i][0] = 1

    # 填充剩余格子：从上到下，从左到右
    for i in range(1, m):      # 从第2行开始
        for j in range(1, n):  # 从第2列开始
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    # 右下角就是答案
    return dp[m-1][n-1]

# 测试3行7列
print(unique_paths(3, 7))  # 输出28

带障碍物的版本（扩展）

假设障碍物用 1 表示，可以走的路用 0 表示。我们需要判断每个格子是否可通行。

def unique_paths_with_obstacles(grid):
    # grid是二维列表，0表示可通行，1表示障碍物
    m = len(grid)          # 行数
    n = len(grid[0])       # 列数

    # 如果起点或终点有障碍，直接返回0
    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return 0

    # 创建dp表格，初始化为0
    dp = [[0] * n for _ in range(m)]

    # 初始化第一行：遇到障碍物之前都是1，之后是0
    for j in range(n):
        if grid[0][j] == 1:
            break          # 后面都过不去
        dp[0][j] = 1

    # 初始化第一列：同理
    for i in range(m):
        if grid[i][0] == 1:
            break
        dp[i][0] = 1

    # 填充内部格子
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1:   # 障碍物不可达
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

# 测试：3行3列，中间一个障碍物
test_grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]
print(unique_paths_with_obstacles(test_grid))  # 输出2（绕开障碍的路径）

新手容易犯的错误

忘记初始化第一行和第一列
如果循环从 i=0, j=0 开始，而 dp[0][0] 没有单独处理，会导致计算 dp[0][1] 时取 dp[-1][1] 导致索引越界或错误结果。一定要先给第一行和第一列赋值。
障碍物处理不当
带障碍物时，不仅要让障碍物格子本身为0，还要注意：如果第一行或第一列有障碍物，那么障碍物后面的格子也不能再走了（因为不能绕过去）。上面的代码用 break 正确处理了。
搞错行列顺序
dp[i][j] 中，i 是行索引，j 是列索引。在写循环时，外层通常遍历行 i，内层遍历列 j，这样符合“逐行处理”的习惯。如果反过来，可能导致依赖未计算的值。
起点终点障碍未判断
如果起点或终点本身就是障碍物，那么根本走不了，答案直接为0。很多新手会忘记检查这一点。

完整可运行的代码示例（万能模板）

下面是一个通用的二维动态规划模板，可以处理“求路径数”和“求最小路径和”两种常见问题，注释详细，方便你理解。

def number_of_paths(grid):
    """
    计算从左上角到右下角的路径数（只能向右或向下，障碍物为1）
    """
    m = len(grid)          # 行数
    n = len(grid[0])       # 列数

    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return 0

    dp = [[0] * n for _ in range(m)]   # 创建dp表格

    # 初始化第一行
    for j in range(n):
        if grid[0][j] == 1:
            break
        dp[0][j] = 1

    # 初始化第一列
    for i in range(m):
        if grid[i][0] == 1:
            break
        dp[i][0] = 1

    # 填充内部
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]


def min_path_sum(grid):
    """
    计算从左上角到右下角的最小路径和（每一步只能向右或向下）
    """
    m = len(grid)          # 行数
    n = len(grid[0])       # 列数

    # 创建dp表格，初始化为0
    dp = [[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 i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[m-1][n-1]


# ===== 测试 =====
# 测试1：无障碍路径数
print("3行7列路径数:", number_of_paths([[0]*7 for _ in range(3)]))   # 28

# 测试2：带障碍路径数
test_grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]
print("带障碍路径数:", number_of_paths(test_grid))   # 2

# 测试3：最小路径和
cost_grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print("最小路径和:", min_path_sum(cost_grid))       # 1→3→1→1→1 = 7

二维动态规划——像走棋盘一样找最优解