Сложность: hard
Дана матрица 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.
👨💻 Алгоритм:
1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2).
2⃣Итеративно заполните dp, начиная с нижней строки, вычисляя для каждой клетки максимальное количество вишен, которое можно собрать с учетом возможных перемещений роботов.
3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов.
😎 Решение:
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 = 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];
}
}Ставь 👍 и забирай 📚 Базу знаний