网格DP

一种常见的 DP 问题模型涉及由方格组成的二维网格（类似方格纸），并要求分析“路径”。路径是一串格子，移动被限制为 $x$ 轴上的一个方向和 $y$ 轴上的一个方向（例如只能向下或向右）。路径通常还要从网格的一个角出发，在另一个角结束。题目可能要求统计满足某种性质的路径数量，也可能要求在所有路径中最大化或最小化某个量。

这类 DP 的子问题通常对应整个网格的一个子矩形。例如，考虑这样的问题：只能沿 $x$ 轴和 $y$ 轴正方向移动，统计从 $(1,1)$ 到 $(N,M)$ 的路径数量。

令 $\texttt{dp}[x][y]$ 为两个角分别是 $(1,1)$ 和 $(x,y)$ 的子矩形中的路径数量。 $\texttt{dp}[x][y]$ 统计的路径首格是 $(1,1)$ ，末格是 $(x,y)$ ，而倒数第二格只能是 $(x-1,y)$ 或 $(x,y-1)$ 。因此，在所有终止于这两个格子的路径后附加 $(x,y)$ ，就能构造终止于 $(x,y)$ 的路径。由此得到递推式 $\texttt{dp}[x][y]=\texttt{dp}[x-1][y]+\texttt{dp}[x][y-1]$ ，并可用它计算 $\texttt{dp}[N][M]$ 。注意 $\texttt{dp}[1][1]=1$ ，因为到 $(1,1)$ 的路径只有这一个格子。一般而言，思考如何向路径末尾添加格子，有助于构造正确的 DP 递推式。

使用 DP 递推式时，必须按适当顺序计算，使某个格子的 DP 值在被用于计算其他格子前已经求出。在上面的示例中，可以从 $1$ 到 $M$ 依次遍历每一行：

	for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            if (j > 1) dp[j][i] += dp[j - 1][i];
            if (i > 1) dp[j][i] += dp[j][i - 1];
        }
}

注意，代码中的坐标形式为（ $x$ 坐标， $y$ 坐标）。大多数时候，把点表示为（行，列）更方便，这会交换坐标顺序；但为与 $\texttt{dp}[x][y]$ 的定义一致，代码使用前一种格式。

问题1

考虑一个 $n \times n$ 的网格，其中一些格子可能设有陷阱。你不能移动到设有陷阱的格子。

你的任务是计算从左上角格子到右下角格子的路径数量。每一步只能向右或向下移动。

解法

本题直接给出一个二维方格网格，要求统计从一个角到另一个角、只能向下（ $y$ 轴正方向）和向右（ $x$ 轴正方向）移动的路径数量。特殊之处在于，路径不能经过标有星号的格子。

原递推式几乎可以直接使用，但需要稍作修改。如果格子 $(x,y)$ 正常，就照常使用递推式；如果它带有星号，则 DP 值为 $0$ ，因为路径不能以陷阱格子结尾。

\texttt{dp}[x][y] = \begin{cases} \texttt{dp}[x-1][y] + \texttt{dp}[x][y-1] & \text{if $(x, y)$ is not a trap} \\ 0, & \text{if $(x, y)$ is a trap} \end{cases}

问题2

给定两个序列 $X＝<x_1，x_2，…，x_m>$ 和 $Y=<y_1,y_2…．y_n>$ ．要求找出 $X$ 和 $Y$ 的一个最长公共子序列。

最长公共子序列是经典字符串问题，但网格在哪里呢？

事实上，可以构造一个网格来解决它。考虑下面的算法，用于构造字符串 $A,B$ 的任意公共子序列（不一定最长）：

从两个指针 $i,j$ 开始，二者初值均为 $0$ 。
每一步执行一次“操作”，直到没有可用操作。“操作”可以是以下任意一种：

将 $i$ 加 $1$ （仅当 $i<|A|$ 时可用）。
将 $j$ 加 $1$ （仅当 $j<|B|$ 时可用）。
仅当 $A_i=B_j$ 时，同时将 $i,j$ 加 $1$ ，并把字符 $A_i$ （或 $B_j$ ）加入公共子序列（仅当 $i<|A|$ 且 $j<|B|$ 时可用）。

该过程会产生公共子序列，因为它从左到右寻找两个字符串共有的字符。

该算法也可以在网格上表示。令 $A:=xabcd$ 、 $B:=yazc$ 。算法的当前状态可由前述 $i,j$ 所确定的点 $(i,j)$ 表示。增加指针可视为向右移动（增加 $i$ ）、向下移动（增加 $j$ ）或斜向移动（同时增加 $i,j$ ）。每次斜向移动都会使公共子序列长度加一。

现在，把“最长公共子序列的长度”改述为：“网格上从左上角到右下角的路径中，‘斜向移动’ （上述算法的操作 3）的最大次数”。这样就构造出了网格型 DP 问题。

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

在上面的网格中，粗体路径在字符“a”和“c”处发生斜向移动。这意味着“xabcd”和“yazc”的最长公共子序列是“ac”。

根据这三种“操作”（也就是路径的三种可能移动），可以构造求最长公共子序列的 DP 递推式：

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

问题1​

解法​

问题2​

问题1

解法

问题2