arpit_aditya's blog

Cherry Pickup Leetcode 741 — Why is this approach giving wrong Answer?
By arpit_aditya, history, 9 months ago, In English

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?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my solution — 

class Solution {
private:
    vector<vector<vector<vector<int>>>> dp;
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        dp.resize(n, vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(n, -1))));
        return max(0, dfs(grid, 0, 0, 0, 0, n));
    }

    int dfs(vector<vector<int>>& grid, int r1, int c1, int r2, int c2, int n) {
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return INT_MIN;
        }
        if (r1 == n - 1 && c1 == n - 1) {
            return grid[r1][c1];
        }
        if (r2 == n - 1 && c2 == n - 1) {
            return grid[r2][c2];
        }
        if (dp[r1][c1][r2][c2] != -1) {
            return dp[r1][c1][r2][c2];
        }
        int cherries = grid[r1][c1] + (r1 != r2 || c1 != c2 ? grid[r2][c2] : 0);
        int maxCherries = max(
            max(dfs(grid, r1 + 1, c1, r2 + 1, c2, n), dfs(grid, r1, c1 + 1, r2, c2 + 1, n)),
            max(dfs(grid, r1 + 1, c1, r2, c2 + 1, n), dfs(grid, r1, c1 + 1, r2 + 1, c2, n))
        );
        dp[r1][c1][r2][c2] = cherries + maxCherries;
        return dp[r1][c1][r2][c2];
    }
};
→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, you are using same approach assuming two paths starting from 0,0 to n-1,n-1 but I'm using two paths that are 0,0 to n-1,n-1 and other one from n-1,n-1 to 0,0. If I use two paths from 0,0 to n-1 n-1 this same code is giving correct answer. But I want to know why can't I travel from 0,0 to n-1, n-1 and n-1,n-1 to 0,0 simultaneously?

    → Reply