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

<p>You have two robots that can collect cherries for you:</p>

<ul>
	<li><strong>Robot #1</strong> is located at the <strong>top-left corner</strong> <code>(0, 0)</code>, and</li>
	<li><strong>Robot #2</strong> is located at the <strong>top-right corner</strong> <code>(0, cols - 1)</code>.</li>
</ul>

<p>Return <em>the maximum number of cherries collection using both robots by following the rules below</em>:</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/29/sample_1_1802.png" style="width: 374px; height: 501px;" />
<pre>
<strong>Input:</strong> grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
<strong>Output:</strong> 24
<strong>Explanation:</strong> Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/sample_2_1802.png" style="width: 500px; height: 452px;" />
<pre>
<strong>Input:</strong> 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]]
<strong>Output:</strong> 28
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>rows == grid.length</code></li>
	<li><code>cols == grid[i].length</code></li>
	<li><code>2 &lt;= rows, cols &lt;= 70</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 100</code></li>
</ul>

class Solution {
public:
    vector<vector<int>> mat;
    int n;
    int m;
    vector<vector<vector<int>>> dp; // Memoization table

    int solve(int i, int j, int k) {
        // Base case: if we reach beyond the last row
        if (i >= n) {
            return 0;
        }

        // Check if the result is already computed for this state
        if (dp[i][j][k] != -1) {
            return dp[i][j][k];
        }

        // Cherry picked by the two robots
        int cherryPicked1 = mat[i][j];
        int cherryPicked2 = (j == k) ? 0 : mat[i][k];

        // Initialize variables for the next row movements
        int down1 = 0, down2 = 0, down3 = 0;
        int diagonalLeft1 = 0, diagonalLeft2 = 0, diagonalLeft3 = 0;
        int diagonalRight1 = 0, diagonalRight2 = 0, diagonalRight3 = 0;

        // Compute all possible movements for the robots
        if (i < n - 1) {
            if (j > 0) {
                if (k > 0) diagonalLeft1 = solve(i + 1, j - 1, k - 1);
                if (k < m - 1) diagonalLeft2 = solve(i + 1, j - 1, k + 1);
                diagonalLeft3 = solve(i + 1, j - 1, k);
            }
            if (j < m - 1) {
                if (k > 0) diagonalRight1 = solve(i + 1, j + 1, k - 1);
                if (k < m - 1) diagonalRight2 = solve(i + 1, j + 1, k + 1);
                diagonalRight3 = solve(i + 1, j + 1, k);
            }
            if (k > 0) down1 = solve(i + 1, j, k - 1);
            if (k < m - 1) down2 = solve(i + 1, j, k + 1);
            down3 = solve(i + 1, j, k);
        }

        // Calculate the maximum cherries that can be picked from all movements
        int maxDown = max(down1, max(down2, down3));
        int maxDiagonalLeft = max(diagonalLeft1, max(diagonalLeft2, diagonalLeft3));
        int maxDiagonalRight = max(diagonalRight1, max(diagonalRight2, diagonalRight3));

        // Store the result in the DP table and return it
        return dp[i][j][k] = cherryPicked1 + cherryPicked2 + max(maxDown, max(maxDiagonalLeft, maxDiagonalRight));
    }

    int cherryPickup(vector<vector<int>>& grid) {
        mat = grid;
        n = grid.size();
        m = grid[0].size();

        // Initialize the memoization table with -1 (indicating not computed yet)
        dp = vector<vector<vector<int>>>(n, vector<vector<int>>(m, vector<int>(m, -1)));

        // Start solving from the top-left corner for both robots
        return solve(0, 0, m - 1);
    }
};

18997