1463. Cherry Pickup II
leetcode hard
Task
Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j).
У вас есть два робота, которые могут собирать вишни:
Робот №1 находится в левом верхнем углу (0, 0), а
Робот №2 находится в правом верхнем углу (0, cols - 1).
Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам:
Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1).
Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой.
Когда оба робота находятся в одной клетке, только один из них собирает вишни.
Оба робота не могут выходить за пределы матрицы в любой момент времени.
Оба робота должны достичь нижней строки в матрице grid.
Пример:
Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.
C# solution
matched/originalpublic class Solution {
public int CherryPickup(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int[,,] dp = new int[m, n, n];
for (int row = m - 1; row >= 0; row--) {
for (int col1 = 0; col1 < n; col1++) {
for (int col2 = 0; col2 < n; col2++) {
int result = grid[row][col1];
if (col1 != col2) {
result += grid[row][col2];
}
if (row != m - 1) {
int maxCherries = 0;
for (int newCol1 = col1 - 1; newCol1 <= col1 + 1; newCol1++) {
for (int newCol2 = col2 - 1; newCol2 <= col2 + 1; newCol2++) {
if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
maxCherries = Math.Max(maxCherries, dp[row + 1, newCol1, newCol2]);
}
}
}
result += maxCherries;
}
dp[row, col1, col2] = result;
}
}
}
return dp[0, 0, n - 1];
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int CherryPickup(int[][] grid) {
int m = grid.size();
int n = grid[0].size();
int[,,] dp = new int[m, n, n];
for (int row = m - 1; row >= 0; row--) {
for (int col1 = 0; col1 < n; col1++) {
for (int col2 = 0; col2 < n; col2++) {
int result = grid[row][col1];
if (col1 != col2) {
result += grid[row][col2];
}
if (row != m - 1) {
int maxCherries = 0;
for (int newCol1 = col1 - 1; newCol1 <= col1 + 1; newCol1++) {
for (int newCol2 = col2 - 1; newCol2 <= col2 + 1; newCol2++) {
if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
maxCherries = max(maxCherries, dp[row + 1, newCol1, newCol2]);
}
}
}
result += maxCherries;
}
dp[row, col1, col2] = result;
}
}
}
return dp[0, 0, n - 1];
}
}Java solution
matched/originalclass Solution {
public int cherryPickup(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int dp[][][] = new int[m][n][n];
for (int row = m - 1; row >= 0; row--) {
for (int col1 = 0; col1 < n; col1++) {
for (int col2 = 0; col2 < n; col2++) {
int result = 0;
result += grid[row][col1];
if (col1 != col2) {
result += grid[row][col2];
}
if (row != m - 1) {
int max = 0;
for (int newCol1 = col1 - 1; newCol1 <= col1 + 1; newCol1++) {
for (int newCol2 = col2 - 1; newCol2 <= col2 + 1; newCol2++) {
if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
max = Math.max(max, dp[row + 1][newCol1][newCol2]);
}
}
}
result += max;
}
dp[row][col1][col2] = result;
}
}
}
return dp[0][0][n - 1];
}
}JavaScript solution
matched/originalclass Solution {
cherryPickup(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = Array.from({ length: m }, () => Array.from({ length: n }, () => Array(n).fill(0)));
for (let row = m - 1; row >= 0; row--) {
for (let col1 = 0; col1 < n; col1++) {
for (let col2 = 0; col2 < n; col2++) {
let result = grid[row][col1];
if (col1 !== col2) {
result += grid[row][col2];
}
if (row !== m - 1) {
let maxCherries = 0;
for (let newCol1 = col1 - 1; newCol1 <= col1 + 1; newCol1++) {
for (let newCol2 = col2 - 1; newCol2 <= col2 + 1; newCol2++) {
if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
maxCherries = Math.max(maxCherries, dp[row + 1][newCol1][newCol2]);
}
}
}
result += maxCherries;
}
dp[row][col1][col2] = result;
}
}
}
return dp[0][0][n - 1];
}
}Python solution
matched/originalclass Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[[0] * n for _ in range(n)] for _ in range(m)]
for row in range(m - 1, -1, -1):
for col1 in range(n):
for col2 in range(n):
result = grid[row][col1]
if col1 != col2:
result += grid[row][col2]
if row != m - 1:
max_cherries = 0
for new_col1 in range(col1 - 1, col1 + 2):
for new_col2 in range(col2 - 1, col2 + 2):
if 0 <= new_col1 < n and 0 <= new_col2 < n:
max_cherries = max(max_cherries, dp[row + 1][new_col1][new_col2])
result += max_cherries
dp[row][col1][col2] = result
return dp[0][0][n - 1]Go solution
matched/originalfunc cherryPickup(grid [][]int) int {
m, n := len(grid), len(grid[0])
dp := make([][][]int, m)
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, n)
}
}
for row := m - 1; row >= 0; row-- {
for col1 := 0; col1 < n; col1++ {
for col2 := 0; col2 < n; col2++ {
result := grid[row][col1]
if col1 != col2 {
result += grid[row][col2]
}
if row != m - 1 {
maxCherries := 0
for newCol1 := col1 - 1; newCol1 <= col1 + 1; newCol1++ {
for newCol2 := col2 - 1; newCol2 <= col2 + 1; newCol2++ {
if newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n {
maxCherries = max(maxCherries, dp[row + 1][newCol1][newCol2])
}
}
}
result += maxCherries
}
dp[row][col1][col2] = result
}
}
}
return dp[0][0][n - 1]
}
func max(x, y int) int {
if x > y {
return x
}
return y
}Explanation
Algorithm
Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2).
Итеративно заполните dp, начиная с нижней строки, вычисляя для каждой клетки максимальное количество вишен, которое можно собрать с учетом возможных перемещений роботов.
Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов.
😎