class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
}
};
741. 摘樱桃
一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：
你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：
示例 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 * N 的二维数组，N的取值范围是1 <= N <= 50。grid[i][j] 都是集合 {-1, 0, 1}其中的一个数。grid[0][0] 和终点 grid[N-1][N-1] 的值都不会是 -1。原站题解
cpp 解法, 执行用时: 18 ms, 内存消耗: 11.5 MB, 提交时间: 2024-05-06 09:56:23
class Solution {
public:
int cherryPickup(vector<vector<int>> &grid) {
int n = grid.size();
vector<vector<int>> f(n, vector<int>(n, INT_MIN));
f[0][0] = grid[0][0];
for (int k = 1; k < n * 2 - 1; ++k) {
for (int x1 = min(k, n - 1); x1 >= max(k - n + 1, 0); --x1) {
for (int x2 = min(k, n - 1); x2 >= x1; --x2) {
int y1 = k - x1, y2 = k - x2;
if (grid[x1][y1] == -1 || grid[x2][y2] == -1) {
f[x1][x2] = INT_MIN;
continue;
}
int res = f[x1][x2]; // 都往右
if (x1) {
res = max(res, f[x1 - 1][x2]); // 往下，往右
}
if (x2) {
res = max(res, f[x1][x2 - 1]); // 往右，往下
}
if (x1 && x2) {
res = max(res, f[x1 - 1][x2 - 1]); // 都往下
}
res += grid[x1][y1];
if (x2 != x1) { // 避免重复摘同一个樱桃
res += grid[x2][y2];
}
f[x1][x2] = res;
}
}
}
return max(f.back().back(), 0);
}
};
cpp 解法, 执行用时: 27 ms, 内存消耗: 36.8 MB, 提交时间: 2024-05-06 09:55:56
class Solution {
public:
int cherryPickup(vector<vector<int>> &grid) {
int n = grid.size();
vector<vector<vector<int>>> f(n * 2 - 1, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
f[0][0][0] = grid[0][0];
for (int k = 1; k < n * 2 - 1; ++k) {
for (int x1 = max(k - n + 1, 0); x1 <= min(k, n - 1); ++x1) {
int y1 = k - x1;
if (grid[x1][y1] == -1) {
continue;
}
for (int x2 = x1; x2 <= min(k, n - 1); ++x2) {
int y2 = k - x2;
if (grid[x2][y2] == -1) {
continue;
}
int res = f[k - 1][x1][x2]; // 都往右
if (x1) {
res = max(res, f[k - 1][x1 - 1][x2]); // 往下，往右
}
if (x2) {
res = max(res, f[k - 1][x1][x2 - 1]); // 往右，往下
}
if (x1 && x2) {
res = max(res, f[k - 1][x1 - 1][x2 - 1]); // 都往下
}
res += grid[x1][y1];
if (x2 != x1) { // 避免重复摘同一个樱桃
res += grid[x2][y2];
}
f[k][x1][x2] = res;
}
}
}
return max(f.back().back().back(), 0);
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 42.4 MB, 提交时间: 2023-06-12 16:02:41
class Solution {
public int cherryPickup(int[][] grid) {
int n = grid.length;
int[][] f = new int[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(f[i], Integer.MIN_VALUE);
}
f[0][0] = grid[0][0];
for (int k = 1; k < n * 2 - 1; ++k) {
for (int x1 = Math.min(k, n - 1); x1 >= Math.max(k - n + 1, 0); --x1) {
for (int x2 = Math.min(k, n - 1); x2 >= x1; --x2) {
int y1 = k - x1, y2 = k - x2;
if (grid[x1][y1] == -1 || grid[x2][y2] == -1) {
f[x1][x2] = Integer.MIN_VALUE;
continue;
}
int res = f[x1][x2]; // 都往右
if (x1 > 0) {
res = Math.max(res, f[x1 - 1][x2]); // 往下，往右
}
if (x2 > 0) {
res = Math.max(res, f[x1][x2 - 1]); // 往右，往下
}
if (x1 > 0 && x2 > 0) {
res = Math.max(res, f[x1 - 1][x2 - 1]); // 都往下
}
res += grid[x1][y1];
if (x2 != x1) { // 避免重复摘同一个樱桃
res += grid[x2][y2];
}
f[x1][x2] = res;
}
}
}
return Math.max(f[n - 1][n - 1], 0);
}
}
python3 解法, 执行用时: 348 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-12 16:02:28
# 优化f[k][x1][x2], 倒序循环x1,x2,优化掉第一维k
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
n = len(grid)
f = [[-inf] * n for _ in range(n)]
f[0][0] = grid[0][0]
for k in range(1, n * 2 - 1):
for x1 in range(min(k, n - 1), max(k - n, -1), -1):
for x2 in range(min(k, n - 1), x1 - 1, -1):
y1, y2 = k - x1, k - x2
if grid[x1][y1] == -1 or grid[x2][y2] == -1:
f[x1][x2] = -inf
continue
res = f[x1][x2] # 都往右
if x1:
res = max(res, f[x1 - 1][x2]) # 往下，往右
if x2:
res = max(res, f[x1][x2 - 1]) # 往右，往下
if x1 and x2:
res = max(res, f[x1 - 1][x2 - 1]) # 都往下
res += grid[x1][y1]
if x2 != x1: # 避免重复摘同一个樱桃
res += grid[x2][y2]
f[x1][x2] = res
return max(f[-1][-1], 0)
golang 解法, 执行用时: 8 ms, 内存消耗: 4.1 MB, 提交时间: 2023-06-12 16:01:15
func cherryPickup(grid [][]int) int {
n := len(grid)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = math.MinInt32
}
}
f[0][0] = grid[0][0]
for k := 1; k < n*2-1; k++ {
for x1 := min(k, n-1); x1 >= max(k-n+1, 0); x1-- {
for x2 := min(k, n-1); x2 >= x1; x2-- {
y1, y2 := k-x1, k-x2
if grid[x1][y1] == -1 || grid[x2][y2] == -1 {
f[x1][x2] = math.MinInt32
continue
}
res := f[x1][x2] // 都往右
if x1 > 0 {
res = max(res, f[x1-1][x2]) // 往下，往右
}
if x2 > 0 {
res = max(res, f[x1][x2-1]) // 往右，往下
}
if x1 > 0 && x2 > 0 {
res = max(res, f[x1-1][x2-1]) // 都往下
}
res += grid[x1][y1]
if x2 != x1 { // 避免重复摘同一个樱桃
res += grid[x2][y2]
}
f[x1][x2] = res
}
}
}
return max(f[n-1][n-1], 0)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
javascript 解法, 执行用时: 100 ms, 内存消耗: 44.2 MB, 提交时间: 2023-06-12 16:00:06
/**
* @param {number[][]} grid
* @return {number}
*/
var cherryPickup = function(grid) {
const n = grid.length;
const f = new Array(n).fill(0).map(() => new Array(n).fill(-Number.MAX_VALUE));
f[0][0] = grid[0][0];
for (let k = 1; k < n * 2 - 1; ++k) {
for (let x1 = Math.min(k, n - 1); x1 >= Math.max(k - n + 1, 0); --x1) {
for (let x2 = Math.min(k, n - 1); x2 >= x1; --x2) {
const y1 = k - x1, y2 = k - x2;
if (grid[x1][y1] === -1 || grid[x2][y2] === -1) {
f[x1][x2] = -Number.MAX_VALUE;
continue;
}
let res = f[x1][x2]; // 都往右
if (x1 > 0) {
res = Math.max(res, f[x1 - 1][x2]); // 往下，往右
}
if (x2 > 0) {
res = Math.max(res, f[x1][x2 - 1]); // 往右，往下
}
if (x1 > 0 && x2 > 0) {
res = Math.max(res, f[x1 - 1][x2 - 1]); //都往下
}
res += grid[x1][y1];
if (x2 !== x1) { // 避免重复摘同一个樱桃
res += grid[x2][y2];
}
f[x1][x2] = res;
}
}
}
return Math.max(f[n - 1][n - 1], 0);
};
javascript 解法, 执行用时: 108 ms, 内存消耗: 49.2 MB, 提交时间: 2023-06-12 15:59:46
/**
* @param {number[][]} grid
* @return {number}
*/
var cherryPickup = function(grid) {
const n = grid.length;
const f = new Array(n * 2 - 1).fill(0).map(() => new Array(n).fill(0).map(() => new Array(n).fill(-Number.MAX_VALUE)));
f[0][0][0] = grid[0][0];
for (let k = 1; k < n * 2 - 1; ++k) {
for (let x1 = Math.max(k - n + 1, 0); x1 <= Math.min(k, n - 1); ++x1) {
const y1 = k - x1;
if (grid[x1][y1] === -1) {
continue;
}
for (let x2 = x1; x2 <= Math.min(k, n - 1); ++x2) {
let y2 = k - x2;
if (grid[x2][y2] === -1) {
continue;
}
let res = f[k - 1][x1][x2]; // 都往右
if (x1 > 0) {
res = Math.max(res, f[k - 1][x1 - 1][x2]); // 往下，往右
}
if (x2 > 0) {
res = Math.max(res, f[k - 1][x1][x2 - 1]); // 往右，往下
}
if (x1 > 0 && x2 > 0) {
res = Math.max(res, f[k - 1][x1 - 1][x2 - 1]); // 都往下
}
res += grid[x1][y1];
if (x2 !== x1) { // 避免重复摘同一个樱桃
res += grid[x2][y2];
}
f[k][x1][x2] = res;
}
}
}
return Math.max(f[n * 2 - 2][n - 1][n - 1], 0);
};
golang 解法, 执行用时: 12 ms, 内存消耗: 6.8 MB, 提交时间: 2023-06-12 15:59:01
func cherryPickup(grid [][]int) int {
n := len(grid)
f := make([][][]int, n*2-1)
for i := range f {
f[i] = make([][]int, n)
for j := range f[i] {
f[i][j] = make([]int, n)
for k := range f[i][j] {
f[i][j][k] = math.MinInt32
}
}
}
f[0][0][0] = grid[0][0]
for k := 1; k < n*2-1; k++ {
for x1 := max(k-n+1, 0); x1 <= min(k, n-1); x1++ {
y1 := k - x1
if grid[x1][y1] == -1 {
continue
}
for x2 := x1; x2 <= min(k, n-1); x2++ {
y2 := k - x2
if grid[x2][y2] == -1 {
continue
}
res := f[k-1][x1][x2] // 都往右
if x1 > 0 {
res = max(res, f[k-1][x1-1][x2]) // 往下，往右
}
if x2 > 0 {
res = max(res, f[k-1][x1][x2-1]) // 往右，往下
}
if x1 > 0 && x2 > 0 {
res = max(res, f[k-1][x1-1][x2-1]) // 都往下
}
res += grid[x1][y1]
if x2 != x1 { // 避免重复摘同一个樱桃
res += grid[x2][y2]
}
f[k][x1][x2] = res
}
}
}
return max(f[n*2-2][n-1][n-1], 0)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
java 解法, 执行用时: 14 ms, 内存消耗: 43.3 MB, 提交时间: 2023-06-12 15:58:38
class Solution {
public int cherryPickup(int[][] grid) {
int n = grid.length;
int[][][] f = new int[n * 2 - 1][n][n];
for (int i = 0; i < n * 2 - 1; ++i) {
for (int j = 0; j < n; ++j) {
Arrays.fill(f[i][j], Integer.MIN_VALUE);
}
}
f[0][0][0] = grid[0][0];
for (int k = 1; k < n * 2 - 1; ++k) {
for (int x1 = Math.max(k - n + 1, 0); x1 <= Math.min(k, n - 1); ++x1) {
int y1 = k - x1;
if (grid[x1][y1] == -1) {
continue;
}
for (int x2 = x1; x2 <= Math.min(k, n - 1); ++x2) {
int y2 = k - x2;
if (grid[x2][y2] == -1) {
continue;
}
int res = f[k - 1][x1][x2]; // 都往右
if (x1 > 0) {
res = Math.max(res, f[k - 1][x1 - 1][x2]); // 往下，往右
}
if (x2 > 0) {
res = Math.max(res, f[k - 1][x1][x2 - 1]); // 往右，往下
}
if (x1 > 0 && x2 > 0) {
res = Math.max(res, f[k - 1][x1 - 1][x2 - 1]); // 都往下
}
res += grid[x1][y1];
if (x2 != x1) { // 避免重复摘同一个樱桃
res += grid[x2][y2];
}
f[k][x1][x2] = res;
}
}
}
return Math.max(f[n * 2 - 2][n - 1][n - 1], 0);
}
}
python3 解法, 执行用时: 336 ms, 内存消耗: 19.3 MB, 提交时间: 2023-06-12 15:58:18
'''
动态规划
f[k][x1][x2]: 两个人A和B分别从(x1, k-x1)何(x2, k-x2)出发，到达(n-1, n-1)摘到最多樱桃个数
'''
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
n = len(grid)
f = [[[-inf] * n for _ in range(n)] for _ in range(n * 2 - 1)]
f[0][0][0] = grid[0][0]
for k in range(1, n * 2 - 1):
for x1 in range(max(k - n + 1, 0), min(k + 1, n)):
y1 = k - x1
if grid[x1][y1] == -1:
continue
for x2 in range(x1, min(k + 1, n)):
y2 = k - x2
if grid[x2][y2] == -1:
continue
res = f[k - 1][x1][x2] # 都往右
if x1:
res = max(res, f[k - 1][x1 - 1][x2]) # 往下，往右
if x2:
res = max(res, f[k - 1][x1][x2 - 1]) # 往右，往下
if x1 and x2:
res = max(res, f[k - 1][x1 - 1][x2 - 1]) # 都往下
res += grid[x1][y1]
if x2 != x1: # 避免重复摘同一个樱桃
res += grid[x2][y2]
f[k][x1][x2] = res
return max(f[-1][-1][-1], 0)
python3 解法, 执行用时: 596 ms, 内存消耗: 71.7 MB, 提交时间: 2023-06-12 15:54:05
from typing import List
from functools import lru_cache
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
@lru_cache(None)
def dfs(r1, c1, r2, c2):
# r1+c1=r2+c2
if r1 < 0 or r2 < 0 or c1 < 0 or c2 < 0 or r1 > rows - 1 or r2 > rows - 1 or c1 > cols - 1 or c2 > cols - 1:
return float('-inf')
if grid[r1][c1] == -1 or grid[r2][c2] == -1:
return float('-inf')
if (r1, c1) == (rows - 1, cols - 1):
return grid[r1][c1]
ans = 0
if (r1, c1) == (r2, c2):
ans += grid[r1][c1]
else:
ans += grid[r1][c1] + grid[r2][c2]
ans += max(dfs(r1 + 1, c1, r2 + 1, c2), dfs(r1, c1 + 1, r2, c2 + 1), dfs(r1 + 1, c1, r2, c2 + 1), dfs(r1, c1 + 1, r2 + 1, c2))
return ans
return max(0, dfs(0, 0, 0, 0))
# s = Solution()
# s.cherryPickup([[0, 1, -1], [1, 0, -1], [1, 1, 1]])