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; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter