摘樱桃
难度:
标签:
题目描述
给你一个 n x 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 个樱桃，这是最大可能值。
示例 2：
输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]] 输出：0
提示：
n == grid.lengthn == grid[i].length1 <= n <= 50grid[i][j]为-1、0或1grid[0][0] != -1grid[n - 1][n - 1] != -1
代码结果
运行时间: 204 ms, 内存: 16.9 MB
/*
* Problem: Same as above.
* Solution using Java Streams for array manipulation.
*/
import java.util.Arrays;
public class CherryPickupStream {
public int cherryPickup(int[][] grid) {
int n = grid.length;
int[][][] dp = new int[n][n][n];
Arrays.stream(dp).forEach(arr2D -> Arrays.stream(arr2D).forEach(arr1D -> Arrays.fill(arr1D, Integer.MIN_VALUE)));
dp[0][0][0] = grid[0][0];
for (int r1 = 0; r1 < n; r1++) {
for (int c1 = 0; c1 < n; c1++) {
for (int r2 = 0; r2 < n; r2++) {
int c2 = r1 + c1 - r2;
if (c2 < 0 || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
continue;
}
int cherries = grid[r1][c1] + (r1 != r2 ? grid[r2][c2] : 0);
int maxCherries = Arrays.stream(new int[]{
r1 > 0 ? dp[r1 - 1][c1][r2] : Integer.MIN_VALUE,
c1 > 0 ? dp[r1][c1 - 1][r2] : Integer.MIN_VALUE,
r2 > 0 ? dp[r1][c1][r2 - 1] : Integer.MIN_VALUE,
c2 > 0 ? dp[r1][c1][r2][c2 - 1] : Integer.MIN_VALUE
}).max().getAsInt();
dp[r1][c1][r2] = maxCherries + cherries;
}
}
}
return Math.max(0, dp[n - 1][n - 1][n - 1]);
}
}
解释
方法:
本题解使用三维动态规划（DP）的方式解决问题。解决的主要策略是同时考虑从(0,0)到(n-1,n-1)的前进路径和从(n-1,n-1)返回到(0,0)的返回路径。这里的关键在于，任何时间点上的两条路径所在的网格之和应该相等。我们使用dp数组，其中dp[t][x1][x2]表示在时间步t，第一条路径在点(x1, t-x1)和第二条路径在点(x2, t-x2)时可以摘到的最大樱桃数。动态规划的转移方程考虑了从左边或上边转移到当前点的所有可能性，同时考虑两个路径可能在同一个点重合的情况。如果两条路径在同一点相遇，则该点的樱桃只计算一次。如果某一步没有有效的移动方式，则直接返回0，表示无法完成任务。
时间复杂度:
O(n^3)
空间复杂度:
O(n^2)
代码细节讲解
🦆
为什么在解决这个问题时选择使用三维动态规划而不是其他算法？
▷🦆
在动态规划转移方程中，为什么要特别处理两条路径在同一点相遇的情况，只计算一次樱桃数？
▷🦆
如何处理边界条件，例如当`x1`或`x2`为0时，以及如何确保不会引用到无效的数组索引？
▷🦆
动态规划数组`dp`中的初始值是如何设置的，为什么只将`dp[0][0][0]`设为`grid[0][0]`？
▷相关问题
最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]] 输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
地下城游戏
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1：
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出：7 解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
示例 2：
输入：dungeon = [[0]] 输出：1
提示：
m == dungeon.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000