You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.


	0 means the cell is empty, so you can pass through,
	1 means the cell contains a cherry that you can pick up and pass through, or
	-1 means the cell contains a thorn that blocks your way.


Return the maximum number of cherries you can collect by following the rules below:


	Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).
	After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.
	When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0.
	If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.


&nbsp;
Example 1:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.


Example 2:

Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0


&nbsp;
Constraints:


	n == grid.length
	n == grid[i].length
	1 &lt;= n &lt;= 50
	grid[i][j] is -1, 0, or 1.
	grid[0][0] != -1
	grid[n - 1][n - 1] != -1


class Solution:
    def cherryPickup(self, grid):
        n = len(grid)
        dp = [[-1] * (n + 1) for _ in range(n + 1)]
        dp[1][1] = grid[0][0]
        for m in range(1, (n << 1) - 1):
            for i in range(min(m, n - 1), max(-1, m - n), -1):
                for p in range(i, max(-1, m - n), -1):
                    j, q = m - i, m - p
                    if grid[i][j] == -1 or grid[p][q] == -1:
                        dp[i + 1][p + 1] = -1
                    else:
                        dp[i + 1][p + 1] = max(dp[i + 1][p + 1], dp[i][p + 1], dp[i + 1][p], dp[i][p])
                        if dp[i + 1][p + 1] != -1: dp[i + 1][p + 1] += grid[i][j] + (grid[p][q] if i != p else 0)
        return max(0, dp[-1][-1])
class Solution {
    public int cherryPickup(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        //For O(N^3) Dp sapce solution
        dp2  = new Integer[m][n][m];
        int ans=solve2(0,0,0,grid,0,m,n);
        if(ans==Integer.MIN_VALUE) return 0;
        return ans;
    }
   
    private Integer[][][] dp2;
    private int solve2(int x1, int y1, int x2, int[][] g, int cpsf, int m, int n){
        int y2 = x1+y1+-x2;
        if(x1>=m||x2>=m||y1>=n||y2>=n||g[x1][y1]==-1||g[x2][y2]==-1) return Integer.MIN_VALUE;
        if(x1==m-1&&y1==n-1) return g[x1][y1];
        //If both p1 and p2 reach (m-1,n-1)
        if(dp2[x1][y1][x2]!=null) return dp2[x1][y1][x2];
        int cherries=0;
        //If both p1 and p2 are at same position then we need to add the cherry only once.
        if(x1==x2&&y1==y2){
            cherries+=g[x1][y1];
        }
        //If p1 and p2 are at different positions then repective cherries can be added.
        else{
            cherries+=g[x1][y1]+g[x2][y2];
        }
        //4 possibilites for p1 and p2 from each point
        int dd=solve2(x1+1,y1,x2+1,g,cpsf+cherries,m,n); //both moves down
        int dr=solve2(x1+1,y1,x2,g,cpsf+cherries,m,n);   //p1 moves down and p2 moves right
        int rr=solve2(x1,y1+1,x2,g,cpsf+cherries,m,n);  //both moves right 
        int rd=solve2(x1,y1+1,x2+1,g,cpsf+cherries,m,n); //p1 moves right and p2 moves down
        
        //We take maximum of 4 possiblities
        int max=Math.max(Math.max(dd,dr), Math.max(rr,rd));
        if(max==Integer.MIN_VALUE) return dp2[x1][y1][x2]=max;
        return dp2[x1][y1][x2]=cherries+=max;
    }
}
class Solution {
public:
    
    int solve(int r1,int c1,int r2,vector<vector<int>>& grid, vector<vector<vector<int>>> &dp)
    {
        //Calculating c2 : 
        /*
        (r1 + c1) = (r2 + c2)
        c2 = (r1 + c1) - r2
        */
        int c2 = (r1+c1)-r2 ; 
        
        //Base condition
if(r1 >= grid.size() || r2 >= grid.size() || c1 >= grid[0].size() || c2 >= grid[0].size() ||                  grid[r1][c1] == -1 || grid[r2][c2] == -1)
    {
        return INT_MIN;
    }
        if(r1 == grid.size()-1 && c1 == grid[0].size()-1)
        {   
            return grid[r1][c1] ;
        }
        
        if(dp[r1][c1][r2] != -1)
        {
            return dp[r1][c1][r2];
        }
        int ch = 0;
        if(r1 == r2 && c1 == c2)
        {
            ch += grid[r1][c1];     
            //if both players are at the same place than collect cherry only one time.
        }
        else
        {
            ch += grid[r1][c1] + grid[r2][c2];
        }
        cout<<ch<<"\n";
        
        //Trying all the possible paths for both the players
        
        int hh = solve(r1, c1+1, r2, grid, dp);
        int vh = solve(r1+1, c1, r2, grid, dp);
        int vv = solve(r1+1, c1, r2+1, grid, dp);
        int hv = solve(r1, c1+1, r2+1, grid, dp);
        
        //collecting maximum cherries from possible paths
        ch += max(max(hh, vh),max(vv, hv)) ; 
        
        dp[r1][c1][r2] = ch;
        
        return ch;    
    }

    
    int cherryPickup(vector<vector<int>>& grid) 
    {
        
        int n = grid.size();
        
        vector<vector<vector<int>>>dp(n, vector<vector<int>>(n, vector<int>(n,-1)));
        
        int ans = solve(0,0,0,grid,dp) ;
        
        if(ans == INT_MIN || ans <0)
        {
            return 0;
        }
        
        return ans;       
        
    }
};
var cherryPickup = function(grid) {
    let result = 0, N = grid.length, cache = {}, cherries;
    
    const solve = (x1, y1, x2, y2) => {
        if(x1 === N -1 && y1 === N-1) 
            return grid[x1][y1] !== -1 ? grid[x1][y1] : -Infinity;
        if(x1 > N -1 || y1 > N-1 || x2 > N-1 || y2 > N-1 || grid[x1][y1] === -1 ||grid[x2][y2] === -1) 
            return -Infinity;
        
        let lookup_key = `${x1}:${y1}:${x2}:${y2}`;
        if(cache[lookup_key]) return cache[lookup_key];
        
        if(x1 === x2 && y1 === y2) 
            cherries = grid[x1][y1];
        else
            cherries = grid[x1][y1] + grid[x2][y2];
        
        result = cherries + Math.max(solve(x1 + 1, y1, x2 + 1, y2),
                solve(x1, y1 + 1, x2, y2 + 1),
                solve(x1 + 1, y1, x2, y2 + 1),
                solve(x1, y1 + 1, x2 + 1, y2));
        
        cache[lookup_key] = result;
        return result;
    };
    
    result = solve(0, 0, 0, 0);
    return result > 0 ? result : 0;
};
Cherry Pickup