Задача: 1463. Cherry Pickup II
Сложность: 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 {
    function cherryPickup($grid) {
        $m = count($grid);
        $n = count($grid[0]);
        $dp = array_fill(0, $m, array_fill(0, $n, array_fill(0, $n, 0)));
        
        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];
    }
}

Ставь 👍 и забирай 📚 Базу знаний