1463. Cherry Pickup II

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

• Robot #1 is located at the top-left corner (0, 0), and
• Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

• From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
• When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
• When both robots stay in the same cell, only one takes the cherries.
• Both robots cannot move outside of the grid at any moment.
• Both robots should reach the bottom row in grid.

class Solution {
    int dp[70][70][70];
    int dfs(vector<vector<int>>& grid, int n, int m, int r, int c1, int c2) {
        if(r == n) return 0;
        if(dp[r][c1][c2] != -1) return dp[r][c1][c2];
        int res = 0;
        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
                int nc1 = c1 + i, nc2 = c2 + j;
                if(0 <= nc1 && nc1 < m && 0 <= nc2 && nc2 < m) {
                    res = max(res, dfs(grid, n, m, r + 1, nc1, nc2));
                }
            }
        }
        return dp[r][c1][c2] = res + (c1 == c2 ? grid[r][c1] : grid[r][c1] + grid[r][c2]); 
    }
public:
    int cherryPickup(vector<vector<int>>& grid) {
        memset(dp, -1, sizeof(dp));
        return dfs(grid, grid.size(), grid[0].size(), 0, 0, grid[0].size() - 1);
    }
};