Q14 Cherry Pickup - Coding Ninjas

 import java.util.* ;
import java.io.*; 
public class Solution {
	public static int maximumChocolates(int r, int c, int[][] grid) {
		/* fixed starting point , variable ending point so we make recursion 
		according to fixed point

		find all combination of paths of alice and bob and return max of them
		*/
		int m = grid.length , n = grid[0].length;
		// return solve(grid , 0 , 0 , n-1 , new Integer[m][n][n]);

		//tabulization
		/* every coloumn signifies if alice and bob were to start with that row and
		col1 & col2 respectively what is the maximum sum they could make till the last
		row;
		*/
		int[][][] dp = new int[m][n][n];
		for(int i = m-1 ;i >= 0 ; i-- ){
			for(int j = n-1 ; j>=0;j-- ){
				for(int k = n-1 ;k>=0 ;k--){
					
					//base case
					if(i == m-1){
						if(j == k)
						dp[i][j][k] = grid[i][j];

						else
						dp[i][j][k] = grid[i][j] + grid[i][k];
					}
					else{
						int maxi = (int)-1e8;	
						for(int c1 : dir){
							for(int c2 : dir ){
								//faith call from Root(0) to all 9 combinations of alice and bob
								int val = (int) -1e8;
								if(j+c1 >= 0 && j+c1 < n && k+c2 >=0 && k+c2 < n) 
								val = dp[i+1][j+c1][k+c2];

								maxi = Math.max(maxi ,val);
							}
						}
						
						if(j == k)
						maxi += grid[i][j];
						
						else
						maxi += grid[i][j] + grid[i][k];

						dp[i][j][k] = maxi;
					}
				}
			}
		}
		
		return dp[0][0][n-1];
	}

	
	//recursion-> 9^(m*n) Memoization -> 9*m*n | Sc - m*n + m*n
	public static int[] dir = {-1,0,1};
	public static int solve(int[][] grid , int r , int c1 , int c2 , Integer[][][] dp){
		if(c1 < 0 || c2 < 0 || c1 >= grid[0].length || c2 >= grid[0].length)
		return (int)-1e8;

		if(r == grid.length - 1){
			if(c1 == c2)
			return grid[r][c1];
		
			else
			return grid[r][c1] + grid[r][c2];
		}
		if(dp[r][c1][c2] != null)
		return dp[r][c1][c2];

		//dont put INT_MIN ever as that might cause integer overflow for a negative value
		int maxi = (int)-1e8;	
		for(int i : dir){
			for(int j : dir ){
				//faith call from Root(0) to all 9 combinations of alice and bob
				int val = solve(grid , r+1 , c1+i , c2 + j , dp);
				maxi = Math.max(maxi ,val);
			}
		}

		//if both are on the same cell , take it once
		if(c1 == c2)
		maxi += grid[r][c1];
		
		else
		maxi += grid[r][c1] + grid[r][c2];

		return dp[r][c1][c2] = maxi;
	}
}