<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 {
    /*
    robot 1 can have its own maximum path and robot 2 can have its own maximum path
    So what if we want to find their maximum values separately
    but we cannot do that in one recursive function it will be very messy or not possible
    lets say we argue that in one function we have 2 for loops one for robot1 and other for robot2
    but that would be very messy because lets say are trying to solve for robot 2 and when we do 
    a recursive call we end up again facing the for loop of robot 1
    so the only way to do is to have 2 separate recursive functions and then add their final return values
    But this also has a problem, we wont be able to maintain the cells that are visited by both r1 and r2
    because if r1 and r2 visit same cell then we are suppose to calculate the nimber of cherries for that
    cell only once.

    Hence the best way to do is manage both of them is simultaneously

    suppose r1 is at index a,b and r2 is at index c,d
    so if we want to get the maximum possible cherries that can be picked by both r1 and r2
    then how many possibilities do we have?
    r1 has 3 paths from a,b and r2 has 3 paths from c,d
    if r1 takes 1 path then which path will r2 take?
    r2 can take any of the three possible paths
    hence for every path of r1 we have 3 paths of r2 and vice versa
    hence we have 9 possibilities

    think in this way, suppose we only has 1 robot
    then it would have 2 possibilities, we would find the maximum from those 3,if we are doing top-down
    the we will further recurse for those 3 and when after base case we return with the values for those 3 
    paths and take maximum to be added to current cell.

    but here we are looking at their maximum or total possible cherries that can be picked by r1 and r2
    together at the same time.

    again lets say r1 is at position a,b and r2 is at position c,d
    so the number of cherries they will pick together is difenitely ab + cd
    but then what about the cherries from the next paths?
    we have to add the ab+cd further to the maximum from next possible paths
    since we are considering them together hence the next possible paths will be all
    the possibilities that can happen for r1 and r2.

    now for r1 and r2 at the same cell:
    in the above lines we said that we will def add the values of cherries at the current pos
    that is ab+cd
    but what is both their pos are equal then we will only add ab or cd

    base case:
    if r1 and r2 are at the last row, then we can directly ad the current cell values because
    they are not going to explore after the last row
    hence ew return grid[m-1][j1] + grid[m-1][j2]
    here also it is possible that they are at the equal cells at the last row.

    tc : o(mnn) for memoization
    tc : o(9^(n*m)) for recursion
    */
public:
    int helper(int i, int j1, int j2, vector<vector<int>>& grid, int m, int n,vector<vector<vector<int>>>& dp)
    {
        if(j1<0 || j2<0 || j1>=n || j2>=n)
        {
            return 0;
        }

        if(i==m-1)
        {
            if(j1==j2)
            {
                return grid[i][j1];
            }
            else
            {
                return grid[i][j1]+grid[i][j2];
            }
        }

        if(dp[i][j1][j2]!=-1)
        {
            return dp[i][j1][j2];
        }

        // down i+1,j
        // diag_left i+1,j-1
        // diag_right i+1,j+1
        // constant change in i, but variable chnage in j in the range {-1,0,1}

        int maxi=-1e8;
        for(int p=-1;p<=+1;p++)
        {
            for(int k=-1;k<=+1;k++)
            {
                int val;
                if(j1==j2)
                {
                    val = grid[i][j1];
                }
                else
                {
                    val = grid[i][j1]+grid[i][j2];
                }
                val+=helper(i+1,j1+p,j2+k,grid,m,n,dp);

                maxi = max(maxi,val);
            }
        }

        return dp[i][j1][j2]=maxi;


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

        vector<vector<vector<int>>> dp (m,vector<vector<int>>(n,vector<int>(n,-1)));

        return helper(0,0,n-1,grid,m,n,dp);

        
    }
};
18207