#1463. Cherry Pickup II

https://leetcode.com/problems/cherry-pickup-ii/description/?envType=daily-question&envId=2024-02-12

/**
 * @param {number[][]} grid
 * @return {number}
 */
function cherryPickup(grid) {
    const m = grid.length;
    const n = grid[0].length;

    // Initialize dp array
    const dp = new Array(m).fill(null).map(() => new Array(n).fill(null).map(() => new Array(n).fill(-1)));

    // Function to calculate maximum cherries
    const maxCherries = (row, col1, col2) => {
        // Base case
        if (row === m) return 0;
        // Check if already visited
        if (dp[row][col1][col2] !== -1) return dp[row][col1][col2];

        let cherries = grid[row][col1];
        if (col1 !== col2) cherries += grid[row][col2];

        let max = 0;
        // Try all possible moves for robot 1 and robot 2
        for (let move1 of [-1, 0, 1]) {
            for (let move2 of [-1, 0, 1]) {
                const newCol1 = col1 + move1;
                const newCol2 = col2 + move2;

                // Check if new positions are valid
                if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
                    max = Math.max(max, maxCherries(row + 1, newCol1, newCol2));
                }
            }
        }

        // Update dp array
        dp[row][col1][col2] = cherries + max;
        return dp[row][col1][col2];
    };

    // Call maxCherries starting from the top row and columns 0 and n-1
    return maxCherries(0, 0, n - 1);
}

Too hard and I am too tired to go over it. Would probably watch a neetcode's video on it.