关于后端:741-摘樱桃-经典线性-DP-运用题

6次阅读

共计 2429 个字符，预计需要花费 7 分钟才能阅读完成。

这是 LeetCode 上的 741. 摘樱桃 ，难度为艰难。

Tag :「线性 DP」

一个 $N \times N$ 的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来示意：

$0$ 示意这个格子是空的，所以你能够穿过它。
$1$ 示意这个格子里装着一个樱桃，你能够摘到樱桃而后穿过它。
$-1$ 示意这个格子里有荆棘，挡着你的路。

你的工作是在恪守下列规定的状况下，尽可能的摘到最多樱桃：

从地位 $(0, 0)$ 登程，最初达到 $(N-1, N-1)$，只能向下或向右走，并且只能穿梭无效的格子（即只能够穿过值为 $0$ 或者 $1$ 的格子）；
当达到 $(N-1, N-1)$ 后，你要持续走，直到返回到 $(0, 0)$，只能向上或向左走，并且只能穿梭无效的格子；
当你通过一个格子且这个格子蕴含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0）；
如果在 $(0, 0)$ 和 $(N-1, N-1)$ 之间不存在一条可通过的门路，则没有任何一个樱桃能被摘到。

示例 1:

输出: grid =
[[0, 1, -1],
 [1, 0, -1],
 [1, 1,  1]]

输入: 5

解释：玩家从（0,0）点登程，通过了向下走，向下走，向右走，向右走，达到了点(2, 2)。在这趟单程中，总共摘到了 4 颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了 1 颗樱桃。在旅程中，总共摘到了 5 颗樱桃，这是能够摘到的最大值了。

阐明:

grid 是一个 $N \times N$ 的二维数组，N 的取值范畴是 $1 <= N <= 50$
每一个 grid[i][j] 都是汇合 {-1, 0, 1} 其中的一个数
能够保障终点 grid[0][0] 和起点 grid[N-1][N-1] 的值都不会是 $-1$

为了不便，咱们令 grid 为 g，同时调整矩阵横纵坐标从 $1$ 开始。

原问题为先从左上角依照「只能往下 + 只能往右」的规定走到右下角，而后再依照「只能往上 + 只能往左」的规定走回左上角，路径的值为 $1$ 的格子得一分（只能得分一次，得分后置零），同时不能通过值为 $-1$ 的格子。

其中第二趟的规定等价于依照第一趟的规定从左上角到右下角再走一遍，再联合每个地位的只能得分一次，能够将原问题等价于：两个点从左上角开始同时走，最终都走到右下角的最大得分。

定义 $f[k][i1][i2]$ 为以后走了 $k$ 步（横纵坐标之和），且第一个点以后在第 $i1$ 行，第二点在第 $i2$ 行时的最大得分，最终答案为 $f[2n][n][n]$，同时有 $f[2][1][1] = g[0][0]$ 的起始状态。

因为两个点是同时走（都走了 $k$ 步），联合「只能往下 + 只能往右」的规定，可间接算得第一个点所在的列为 $j1 = k – i1$，第二点所在的列为 $j2 = k – i2$。

不失一般性思考 $f[k][i1][i2]$ 该如何转移，两个点均有可能走行或走列，即有 $4$ 种前驱状态：$f[k – 1][i1 – 1][i2]$、$f[k – 1][i1 – 1][i2 – 1]$、$f[k – 1][i1][i2 – 1]$ 和 $f[k – 1][i1][i2]$，在四者中取最大值，同时以后地位 $(i1, j1)$ 和 $(i2, j2)$ 的得分须要被累加，假如两者得别离为 $A$ 和 $B$，若两个地位不重叠的话，能够同时累加，否则只能累加一次。

一些细节：为了避免从值为 $-1$ 的格子进行转移影响正确性，咱们须要先将所有 $f[k][i1][i2]$ 初始化为负无穷。

代码：

class Solution {
    static int N = 55, INF = Integer.MIN_VALUE;
    static int[][][] f = new int[2 * N][N][N];
    public int cherryPickup(int[][] g) {
        int n = g.length;
        for (int k = 0; k <= 2 * n; k++) {for (int i1 = 0; i1 <= n; i1++) {for (int i2 = 0; i2 <= n; i2++) {f[k][i1][i2] = INF;
                }
            }
        }
        f[2][1][1] = g[0][0];
        for (int k = 3; k <= 2 * n; k++) {for (int i1 = 1; i1 <= n; i1++) {for (int i2 = 1; i2 <= n; i2++) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 <= 0 || j1 > n || j2 <= 0 || j2 > n) continue;
                    int A = g[i1 - 1][j1 - 1], B = g[i2 - 1][j2 - 1];
                    if (A == -1 || B == -1) continue;
                    int a = f[k - 1][i1 - 1][i2], b = f[k - 1][i1 - 1][i2 - 1], c = f[k - 1][i1][i2 - 1], d = f[k - 1][i1][i2];
                    int t = Math.max(Math.max(a, b), Math.max(c, d)) + A;
                    if (i1 != i2) t += B;
                    f[k][i1][i2] = t;
                }
            }
        }
        return f[2 * n][n][n] <= 0 ? 0 : f[2 * n][n][n];
    }
}