So, I started Learning Dynamic Programming and I came across this question - Cherry Pickup 741
I am following simple approach of walking simultaneously from (0,0)->(N-1,N-1) && (N-1,N-1)->(0,0) if any point they are on the same cell I add it only once.
Here is my code-
class Solution {
public int minCost(int row_start,int col_start,int row_end,int col_end,int grid[][]){
if(row_start==grid.length-1 && col_start==grid[0].length-1){
return grid[row_start][col_start]; //if the first person reaches last cell (n-1,n-1)
}
if(row_end==0 && col_end==0){
return grid[0][0];//if the 2nd person reaches 0,0
}
if(row_start>=grid.length || row_end>=grid.length || col_start>=grid[0].length || col_end>=grid[0].length ||row_start<0 || row_end<0 || col_start<0 || col_end<0){//edge case
return (int)-1e8;
}
if(grid[row_start][col_start]==-1 || grid[row_end][col_end]==-1){
return (int)-1e8;
}
//intialising the vlaues of movement
int right_up=grid[row_start][col_start];
int right_left=grid[row_start][col_start];
int down_up=grid[row_start][col_start];
int down_left=grid[row_start][col_start];
if(row_start==row_end && col_start==col_end){
// if they are on the same cell only add once
right_up=right_up+minCost(row_start,col_start+1,row_end-1,col_end,grid);
right_left=right_left+minCost(row_start,col_start+1,row_end,col_end-1,grid);
down_up=down_up+minCost(row_start+1,col_start,row_end-1,col_end,grid);
down_left=down_left+minCost(row_start+1,col_start,row_end,col_end-1,grid);
}else{
// if they are on different cells add both of them.
right_up=right_up+grid[row_end][col_end]+minCost(row_start,col_start+1,row_end-1,col_end,grid);
right_left=right_left+grid[row_end][col_end]+minCost(row_start,col_start+1,row_end,col_end-1,grid);
down_up=down_up+grid[row_end][col_end]+minCost(row_start+1,col_start,row_end-1,col_end,grid);
down_left=down_left+grid[row_end][col_end]+minCost(row_start+1,col_start,row_end,col_end-1,grid);
}
return Math.max(right_up,Math.max(right_left,Math.max(down_up,down_left)));
}
public int cherryPickup(int[][] grid) {
return minCost(0,0,grid.length-1,grid.length-1,grid);
}
}
This is giving me wrong answer for the first testcase. I have seen some solutions where they are assuming two paths from start to end. saying that moving from (0,0) to (n-1,n-1) is same as going from (n-1,n-1) to (0,0) but then why is my solution giving me wrong answer?