classSolution{publicintcherryPickup(int[][]grid){// was able to understand from the post: https://leetcode.com/problems/cherry-pickup/solutions/329945/very-easy-to-follow-step-by-step-recursi-sjpg///instead of moving from 0,0 and m-1,n-1 at the same time have two people moving from the 0,0 position and at any given point of time if both are at the same cell count onlly once.intn=grid.length;intdp[][][][]=newint[n][n][n][n];for(intdp3[][][]:dp){for(intdp2[][]:dp3){for(intdp1[]:dp2)Arrays.fill(dp1,-1);}}returnMath.max(0,max(0,0,0,0,grid.length,grid,dp));}publicintmax(inti,intj,intk,intl,intn,int[][]grid,int[][][][]dp){//base caseif(i>=n||j>=n||k>=n||l>=n||grid[i][j]==-1||grid[k][l]==-1)returnInteger.MIN_VALUE;if(i==n-1&&j==n-1){returngrid[i][j];// if any one reached the end return the value at the location}if(k==n-1&&l==n-1){returngrid[k][l];// if any one reached the end return the value at the location}if(dp[i][j][k][l]!=-1)returndp[i][j][k][l];intcherries=0;if(i==k&&j==l){cherries+=grid[i][j];//count only once;}else{cherries+=grid[i][j]+grid[k][l];}cherries+=Math.max(max(i+1,j,k+1,l,n,grid,dp),Math.max(max(i+1,j,k,l+1,n,grid,dp),Math.max(max(i,j+1,k+1,l,n,grid,dp),max(i,j+1,k,l+1,n,grid,dp))));returndp[i][j][k][l]=cherries;}}
Top comments (0)
Subscribe
We're a place where coders share, stay up-to-date and grow their careers.
Top comments (0)