
### Problem Statement

###### 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.

**Constraints:**

- rows == grid.length
- cols == grid[i].length
- 2 <= rows, cols <= 70
- 0 <= grid[i][j] <= 100

**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**

![Cherry Pickup Problem](https://assets.leetcode.com/uploads/2020/04/23/sample_2_1802.png)

**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.**

###### SOLUTION

**Steps To Solve**

- Lets start by defining the current state of the robots.
- Both the robots can be at different columns but row will be the same for both.
- So we have 3 states c1,c2,r.
- Since we move robots synchronously, and each robot has three different movements for one step, we totally have **3∗3=9** possible movements for two robots.
- The maximum cherries robots can pick in the future would be the max of those 9 movements, which is the maximum of dp(c1,c2,r), where c1 can be col1, col1+1, or col1-1, and c2 can be col2, col2+1, or col2-1.
- If both the robots land on same block then we add the block value only one time and if not then we add both block values.
- From every block we can go to 3 directions bottom,bottom left and bottom right.
- We calculate the maximum value from all the possibe states the robots can land into.
- The dp function returns the maximum cherries we can pick if robot1 starts at (row, col1) and robot2 starts at (row, col2)
- To avoid repeated calculation we can use memoization.

```js
/**
 * @param {number[][]} grid
 * @return {number}
 */

let dp;
var cherryPickup = function (grid) {
  dp = new Array(80)
    .fill(0)
    .map(() => new Array(80).fill(0).map(() => new Array(80).fill(-1)));
  let m = grid.length;
  let n = grid[0].length;
  return cherry(grid, 0, n - 1, 0);
};

function cherry(grid, c1, c2, r) {
  let m = grid.length;
  let n = grid[0].length;

  if (r === m) return 0;
  if (dp[c1][c2][r] !== -1) return dp[c1][c2][r];

  let ans = 0;

  for (let i = -1; i <= 1; i++) {
    for (let j = -1; j <= 1; j++) {
      let C1 = c1 + i;
      let C2 = c2 + j;

      if (C1 >= 0 && C2 >= 0 && C1 < n && C2 < n) {
        ans = Math.max(ans, cherry(grid, C1, C2, r + 1));
      }
    }
  }

  if (c1 === c2) {
    ans += grid[r][c1];
  } else {
    ans += grid[r][c1] + grid[r][c2];
  }

  return (dp[c1][c2][r] = ans);
}
```

###### Time and Space Complexity

Let M be the number of rows in grid and N be the number of columns in grid.

Time Complexity : **O(MN&sup2;)** , since our helper function have three variables as input, which have M, N, and N possible values respectively. In the worst case, we have to calculate them all once, so that would cost O(M\*N\*N)=**O(MN&sup2;)**. Also, since we save the results after calculating, we would not have repeated calculation.

Space Complexity : **O(MN&sup2;)** , since our helper function have three variables as input, and they have M, N, and N possible values respectively. We need a map with size of O(M\*N\*N)=**O(MN&sup2;)** to store the results.
