03_Paths on Grids 网格路径问题

网格路径问题

Authors: Nathan Chen, Michael Cao, Benjamin Qi, Andrew Wang Contributor: Neo Wang

---

先决条件

• Gold - Introduction to DP (动态规划简介)

---

教程

网格路径问题概述

DP 问题的一个常见原型涉及由正方形单元格组成的 2D 网格（类似于方格纸），我们需要分析”路径”。路径是一系列单元格的序列，其移动仅限于在 x 轴的一个方向和 y 轴的一个方向（例如，你可能只能向下或向右移动）。通常，路径还必须从网格的一个角落开始，并在另一个角落结束。问题可能要求你计算满足某些属性的路径数量，或者可能要求你在所有路径中找到某个量的最大值或最小值。

---

基本网格路径 DP

问题：计算从 (1, 1) 到 (N, M) 的路径数量，只能向正 x 方向和正 y 方向移动。

定义：dp[x][y] 为从 (1, 1) 到 (x, y) 的路径数量

初始条件：dp[1][1] = 1（起点只有一种方式）

状态转移： dp[x][y] = dp[x − 1][y] + dp[x][y − 1]

for i in range(M):
    for j in range(N):
        if j > 0:
            dp[j][i] += dp[j - 1][i]
        if i > 0:
            dp[j][i] += dp[j][i - 1]

注意: 代码中的坐标是以 (x 坐标, y 坐标) 的形式表示的。大多数情况下，将点视为 (行, 列) 更方便，这会交换坐标的顺序。

---

示例 - 网格路径 (Grid Paths)

Focus Problem: 在继续之前，请尽力解决这个问题！

题目描述

在这个问题中，我们直接得到一个二维网格，必须计算从角落到角落的路径数量，这些路径只能向下（正 y 方向）和向右（正 x 方向）移动，有一个特殊的限制：**路径不能使用标有星号 (*) 的单元格**。

解法

定义：dp[i][j] 为到达单元格 (i, j) 的合法路径数量

初始条件：dp[0][0] = 1（起点可达）

状态转移： - 如果单元格 (i, j) 是障碍物：dp[i][j] = 0 - 否则：dp[i][j] = dp[i-1][j] + dp[i][j-1]

$$dp[i][j] = \begin{cases} 0 & \text{if } (i,j) \text{ is a trap} \\ dp[i-1][j] + dp[i][j-1] & \text{otherwise} \end{cases}$$

n = int(input())
ok = [[char == "." for char in input()] for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1

for i in range(n):
    for j in range(n):
        # if current square is a trap
        if not ok[i][j]:
            dp[i][j] = 0
            continue
        if i - 1 >= 0:
            # add paths ending on the square above
            dp[i][j] += dp[i - 1][j]
        if j - 1 >= 0:
            # add paths ending on the square to the left
            dp[i][j] += dp[i][j - 1]
        dp[i][j] %= int(1e9 + 7)

print(dp[n - 1][n - 1])

注意: 在读取输入时，坐标现在是以 (row, column) 的形式出现的。

---

示例 - 最长公共子序列 (Longest Common Subsequence)

Focus Problem: 在继续之前，请尽力解决这个问题！

什么是网格？

最长公共子序列是一个经典的字符串问题，但网格在哪里？实际上，我们可以创建一个网格来解决这个问题。

考虑以下算法来在两个字符串 A 和 B 之间创建任意（不一定是最长）的子序列：

1. 我们用两个指针 i 和 j，每个指针都从 0 开始。
2. 我们在每个时间步执行一些”操作”，直到没有更多的可用”操作”。一个”操作”可以是以下任何一种：
   • 将 i 的值增加 1（仅当 i < |A| 时有效）
   • 将 j 的值增加 1（仅当 j < |B| 时有效）
   • 仅当 A_i = B_j 时，将 i 和 j 的值增加 1，并将那个字符追加到公共子序列中（仅当 i < |A| 和 j < |B| 时有效）

网格表示

这个算法也可以在网格上进行说明。设 A := xabcd 和 B := yazc。然后，算法的当前状态可以用我们之前讨论的 i 和 j 的值定义为一个特定的点 (i, j)。指针增加的过程可以看作是向右移动（如果 i 增加）、向下移动（如果 j 增加）或对角线移动（如果 i 和 j 都增加）。可以看到，每次对角线移动都会使公共子序列的长度增加一。

现在，我们将”最长公共子序列的长度”重新表述为”从网格左上角到右下角路径中的最大’对角线移动’次数”。因此，我们已经构建了一个网格型动态规划问题。

       x    a    b    c    d
y      0    0    0    0    0
a      0    1    1    1    1
z      0    1    1    1    1
c      0    1    1    2    2

在上面的网格中，可以看到加粗的路径在字符 “a” 和 “c” 处有对角线移动。这意味着 “xabcd” 和 “yazc” 之间的最长公共子序列是 “ac”。

解法

定义：dp[i][j] 为 A[0..i-1] 和 B[0..j-1] 的最长公共子序列长度

初始条件：dp[0][j] = dp[i][0] = 0（空串的 LCS 为 0）

状态转移： - 如果 A_i = B_j：dp[i][j] = dp[i-1][j-1] + 1 - 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } A_i = B_j \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}$$

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
        for i in range(1, len(a) + 1):
            for j in range(1, len(b) + 1):
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[len(a)][len(b)]

---

总结

问题类型	状态定义	状态转移
基本网格路径	dp[x][y]: 从 (1, 1) 到 (x, y) 的路径数	dp[x][y] = dp[x − 1][y] + dp[x][y − 1]
带障碍网格	dp[x][y]: 到达 (x, y) 的合法路径数	障碍物处 dp = 0
最长公共子序列	dp[i][j]: A[0..i − 1] 和 B[0..j − 1] 的 LCS 长度	匹配时 +1，否则取最大值

---

经典问题

题目	难度	描述
Grid Paths	Easy	计算带障碍网格的路径数量
Longest Common Subsequence	Easy	计算两个字符串的 LCS 长度