741. Cherry Pickup
leetcode hard
#array#csharp#dynamic-programming#hard#leetcode#math#matrix
Task
Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.
Пример:
Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
C# solution
matched/originalusing System;
public class Solution {
public int CherryPickup(int[][] grid) {
int n = grid.Length;
int[][][] dp = new int[n][][];
for (int i = 0; i < n; i++) {
dp[i] = new int[n][];
for (int j = 0; j < n; j++) {
dp[i][j] = new int[2 * n - 1];
Array.Fill(dp[i][j], int.MinValue);
}
}
dp[0][0][0] = grid[0][0];
for (int k = 1; k < 2 * n - 1; k++) {
for (int i1 = Math.Max(0, k - n + 1); i1 <= Math.Min(n - 1, k); i1++) {
for (int i2 = Math.Max(0, k - n + 1); i2 <= Math.Min(n - 1, k); i2++) {
int j1 = k - i1, j2 = k - i2;
if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
int maxCherries = int.MinValue;
if (i1 > 0 && i2 > 0) maxCherries = Math.Max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]);
if (i1 > 0) maxCherries = Math.Max(maxCherries, dp[i1 - 1][i2][k - 1]);
if (i2 > 0) maxCherries = Math.Max(maxCherries, dp[i1][i2 - 1][k - 1]);
maxCherries = Math.Max(maxCherries, dp[i1][i2][k - 1]);
if (maxCherries != int.MinValue) {
dp[i1][i2][k] = maxCherries + grid[i1][j1];
if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
}
}
}
}
}
return Math.Max(0, dp[n - 1][n - 1][2 * 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 n = grid.size();
int[][][] dp = new int[n][][];
for (int i = 0; i < n; i++) {
dp[i] = new int[n][];
for (int j = 0; j < n; j++) {
dp[i][j] = new int[2 * n - 1];
Array.Fill(dp[i][j], int.MinValue);
}
}
dp[0][0][0] = grid[0][0];
for (int k = 1; k < 2 * n - 1; k++) {
for (int i1 = max(0, k - n + 1); i1 <= min(n - 1, k); i1++) {
for (int i2 = max(0, k - n + 1); i2 <= min(n - 1, k); i2++) {
int j1 = k - i1, j2 = k - i2;
if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
int maxCherries = int.MinValue;
if (i1 > 0 && i2 > 0) maxCherries = max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]);
if (i1 > 0) maxCherries = max(maxCherries, dp[i1 - 1][i2][k - 1]);
if (i2 > 0) maxCherries = max(maxCherries, dp[i1][i2 - 1][k - 1]);
maxCherries = max(maxCherries, dp[i1][i2][k - 1]);
if (maxCherries != int.MinValue) {
dp[i1][i2][k] = maxCherries + grid[i1][j1];
if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
}
}
}
}
}
return max(0, dp[n - 1][n - 1][2 * n - 1]);
}
}Java solution
matched/originalpublic class Solution {
public int cherryPickup(int[][] grid) {
int n = grid.length;
int[][][] dp = new int[n][n][2 * n - 1];
for (int[][] layer : dp) {
for (int[] row : layer) {
Arrays.fill(row, Integer.MIN_VALUE);
}
}
dp[0][0][0] = grid[0][0];
for (int k = 1; k < 2 * n - 1; k++) {
for (int i1 = Math.max(0, k - n + 1); i1 <= Math.min(n - 1, k); i1++) {
for (int i2 = Math.max(0, k - n + 1); i2 <= Math.min(n - 1, k); i2++) {
int j1 = k - i1, j2 = k - i2;
if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
int maxCherries = Integer.MIN_VALUE;
if (i1 > 0 && i2 > 0) maxCherries = Math.max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]);
if (i1 > 0) maxCherries = Math.max(maxCherries, dp[i1 - 1][i2][k - 1]);
if (i2 > 0) maxCherries = Math.max(maxCherries, dp[i1][i2 - 1][k - 1]);
maxCherries = Math.max(maxCherries, dp[i1][i2][k - 1]);
if (maxCherries != Integer.MIN_VALUE) {
dp[i1][i2][k] = maxCherries + grid[i1][j1];
if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
}
}
}
}
}
return Math.max(0, dp[n - 1][n - 1][2 * (n - 1)]);
}
}JavaScript solution
matched/originalvar cherryPickup = function(grid) {
const n = grid.length;
const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => Array(2 * n - 1).fill(-Infinity)));
dp[0][0][0] = grid[0][0];
for (let k = 1; k < 2 * (n - 1) + 1; k++) {
for (let i1 = Math.max(0, k - n + 1); i1 < Math.min(n, k + 1); i1++) {
for (let i2 = Math.max(0, k - n + 1); i2 < Math.min(n, k + 1); i2++) {
const j1 = k - i1, j2 = k - i2;
if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
let maxCherries = Math.max(
i1 > 0 && i2 > 0 ? dp[i1 - 1][i2 - 1][k - 1] : -Infinity,
i1 > 0 ? dp[i1 - 1][i2][k - 1] : -Infinity,
i2 > 0 ? dp[i1][i2 - 1][k - 1] : -Infinity,
dp[i1][i2][k - 1]
);
if (maxCherries != -Infinity) {
dp[i1][i2][k] = maxCherries + grid[i1][j1];
if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
}
}
}
}
}
return Math.max(0, dp[n - 1][n - 1][2 * (n - 1)]);
};Python solution
matched/originaldef cherryPickup(grid):
n = len(grid)
dp = [[[-float('inf')] * n for _ in range(n)] for _ in range(n)]
dp[0][0][0] = grid[0][0]
for k in range(1, 2 * (n - 1) + 1):
for i1 in range(max(0, k - n + 1), min(n, k + 1)):
for i2 in range(max(0, k - n + 1), min(n, k + 1)):
j1, j2 = k - i1, k - i2
if 0 <= j1 < n and 0 <= j2 < n and grid[i1][j1] != -1 and grid[i2][j2] != -1:
max_cherries = max(
dp[i1 - 1][i2 - 1][k - 1] if i1 > 0 and i2 > 0 else -float('inf'),
dp[i1 - 1][i2][k - 1] if i1 > 0 else -float('inf'),
dp[i1][i2 - 1][k - 1] if i2 > 0 else -float('inf'),
dp[i1][i2][k - 1]
)
if max_cherries != -float('inf'):
dp[i1][i2][k] = max_cherries + grid[i1][j1]
if i1 != i2:
dp[i1][i2][k] += grid[i2][j2]
return max(0, dp[n - 1][n - 1][2 * (n - 1)])Go solution
matched/originalpackage main
import "math"
func cherryPickup(grid [][]int) int {
n := len(grid)
dp := make([][][]int, n)
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, 2*n-1)
for k := range dp[i][j] {
dp[i][j][k] = math.MinInt32
}
}
}
dp[0][0][0] = grid[0][0]
for k := 1; k < 2*n-1; k++ {
for i1 := max(0, k-n+1); i1 <= min(n-1, k); i1++ {
for i2 := max(0, k-n+1); i2 <= min(n-1, k); i2++ {
j1, j2 := k-i1, k-i2
if j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1 {
maxCherries := math.MinInt32
if i1 > 0 && i2 > 0 {
maxCherries = max(maxCherries, dp[i1-1][i2-1][k-1])
}
if i1 > 0 {
maxCherries = max(maxCherries, dp[i1-1][i2][k-1])
}
if i2 > 0 {
maxCherries = max(maxCherries, dp[i1][i2-1][k-1])
}
maxCherries = max(maxCherries, dp[i1][i2][k-1])
if maxCherries != math.MinInt32 {
dp[i1][i2][k] = maxCherries + grid[i1][j1]
if i1 != i2 {
dp[i1][i2][k] += grid[i2][j2]
}
}
}
}
}
}
return max(0, dp[n-1][n-1][2*n-1])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}Explanation
Algorithm
Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).
Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.
Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.
😎