741. 摘樱桃 : 经典线性 DP 运用题

741. 摘樱桃 : 经典线性 DP 运用题

题目描述

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

Tag : 「线性 DP」

你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：

示例 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颗樱桃，这是可以摘到的最大值了。

说明:

线性 DP

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

代码：

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

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：​​github.com/SharingSour…​​ 。

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。