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; } }