Q47 Cherry Pickup - LeetCode 741 (recursion approach)

PHOTO EMBED

Thu Mar 30 2023 15:28:25 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

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;
    }
}
content_copyCOPY

https://leetcode.com/problems/cherry-pickup/