Задача: 741. Cherry Pickup
Сложность: hard

Вам дана сетка 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

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

3⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.

😎 Решение:

var 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)]);
};

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