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[x][y]$ 计算的路径中的第一个单元格是 $(1,1)$，且最后一个单元格是 $(x,y)$。然而，倒数第二个单元格可以是 $(x-1,y)$ 或 $(x,y-1)$。因此，如果我们假设将单元格 $(x,y)$ 附加到以 $(x-1,y)$ 或 $(x,y-1)$ 结束的路径上，我们就能构造以 $(x,y)$ 结束的路径。像这样逆向思考，可以引出以下递推关系：

$$dp[x][y] = dp[x-1][y] + dp[x][y-1]$$

请注意，$dp[1][1] = 1$，因为到达 $(1,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$ 方向）移动，有一个特殊的限制：路径不能使用标有星号 (*) 的单元格。

解法

我们几乎可以使用原始递推公式，但我们必须对其进行修改。基本上，如果单元格 $(x,y)$ 是正常的，我们可以正常使用递推公式。但是，如果单元格 $(x,y)$ 有一个星号，dp 值是 $0$，因为没有任何路径可以结束在一个陷阱上。

$$dp[x][y] = \begin{cases} dp[x-1][y] + dp[x][y-1] & \text{if } (x,y) \text{ is not a trap} \\ 0 & \text{if } (x,y) \text{ is a trap} \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 递推关系来找到最长公共子序列：

$$dp[i][j] = \begin{cases} \max(dp[i-1][j], dp[i][j-1]) & \text{if } A_i \neq B_j \\ dp[i-1][j-1] + 1 & \text{if } A_i = B_j \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 长度