Cherry Pickup Leetcode 741 — Why is this approach giving wrong Answer?

Revision en1, by arpit_aditya, 2023-10-29 07:40:14

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?

Tags dynamic programming, backtracking, recursion, memoization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English arpit_aditya 2023-10-29 07:40:14 2910 Initial revision (published)