class Solution {
public int cherryPickup(int[][] grid) {
int n = grid.length;
int[][][][] dp = new int[n][n][n][n];
return cherry(0 , 0 , 0 , 0 , grid , dp , n);
}
public static int cherry(int r1 , int c1 , int r2 , int c2 , int[][] grid ,int[][][][] dp , int n)
{
//if invalid move return -infinity as there is no way to reach last cell
if(r1 >= n || r2 >= n || c1 >= n ||
c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1)
return -1;
//if 1 person is at last cell it means other will also be at last cell
if(r1 == n - 1 && c2 == n - 1)
return grid[r1][c1];
//if answer is already stored in memoization return it
if(dp[r1][c1][r2][c2] != 0)
return dp[r1][c1][r2][c2];
int cherries = 0;
//if both person are at same cell , add it only once
if(r1 == r2 && c1 == c2)
cherries += grid[r1][c1];
else
cherries += grid[r1][c1] + grid[r2][c2];
int f1 = cherry(r1 , c1+1 , r2 , c2+1 , grid,dp,n); //hh
int f2 = cherry(r1 , c1+1 , r2+1 , c2 , grid,dp,n); //hv
int f3 = cherry(r1+1 , c1 , r2+1 , c2 , grid,dp,n); //vv
int f4 = cherry(r1+1 , c1 , r2 , c2+1 , grid,dp,n); //vh
cherries += Math.max(Math.max(f1,f2),Math.max(f3,f4));
dp[r1][c1][r2][c2] = cherries;
return cherries;
}
}
Comments