题目形容

这是 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$

线性 DP

为了不便，咱们令 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];    }}
  • 工夫复杂度：状态数量级为 $n^3$，每个状态转移复杂度为 $O(1)$。整体复杂度为 $O(n^3)$
  • 空间复杂度：$O(n^3)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.741 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地

本文由mdnice多平台公布