Apple Pickup

 The idea is to explore two paths simultaneously from (0,0) to (‘N’-1, ‘N’-1) and collect maximum apples. However, while implementing this approach we may count 1 apple two times, so we need to take care of this problem.

 

Complete Algorithm:

• We will make a helper recursive function named ‘SOLVE’ which will receive 3 parameters ‘R1’, ‘C1’, ‘C2’.
• We will calculate ‘R2’ = ‘R1’+’C1’-’C2’,  (‘R1’+’C1’ ==  ‘R2’+’C2’) because at each step value of 1 variable is increased by 1 from both sides as each person will move 1 step.
• Here (‘R1’, ‘C1’) will point to the current position for the first-person and (‘R2’,’ C2’)  will point to the current position for a second person. All 4 variables will be initialized to a large negative value(INT_MIN).
• Base Case:
  • If  ‘R1’ == ‘N’ -1 and ‘C1’ == ‘N’ -1 then do:
    • Return ‘MATRIX[ R1][C1]’.
  • If ‘R2’ ==  ‘N’-1 and ‘C2’ ==  ‘N’-1 then do:
    • Return ‘MATRIX[ R2][C2]’.
  • If both people are standing on the same point (‘R1’==’R2’ and ‘C1’==’C2’) then do:
    • Return ‘MATRIX[ R2][C2]’.
  • Otherwise do:
    • Return ‘MATRIX[ R1][C1]’ +  ‘MATRIX[ R2][C2]’.

• Recursive Calls:
  • Initialize an integer variable ‘ANS’=0.
  • Now 4 possible combinations can be made :
  • Let ‘DOWN_DOWN’ = Both person go to the Downside.
  • Let ‘RIGHT_DOWN’ =  the First-person goes to the Right side and second to the Downside.
  • Let ‘DOWN_RIGHT’ =  the First person goes to Downside and second to the Right side.
  • Let RIGHT_RIGHT = Both person go to Right side.
  • We can calculate the values of the above variable by making recursive calls.
    • DOWN_DOWN = SOLVE (R1+1, C1, R2+1, C2)
    • RIGHT_DOWN =  SOLVE (R1, C1+1, R2+1, C2)
    • DOWN_RIGHT = SOLVE (R1+1, C1, R2, C2+1)
    • RIGHT_RIGHT = SOLVE (R1, C1+1, R2, C2+1)
• Set ‘ANS’  = ‘ANS’ + the maximum of these 4 variables.
• Return ‘ANS’.

Our last approach was very simple and easy, but its time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization.

We will initialize a 3-D array say ‘MEMO[N][N][N]’ with -1, where ‘N’ is the number of rows and columns. Where ‘MEMO[R1][C1][C2]’ equals -1 means the current state is not explored. Otherwise, ‘MEMO[R1][C1][C2]’ represents the max number of apples that can be collected by 2 people going from ‘R1’, ‘C1’ and ‘R2’, ‘C2’ to ‘N’-1, ‘N’-1.

So there will be two modification to the earlier approach :

1. In Base Case, first of all, we will check the value of ‘MEMO’ if it is not equal to -1, then simply return the value stored in the ‘MEMO’.
2. In Recursive Calls, before returning the ‘ANS’ we will store the value in ‘MEMO’.

 As our earlier approach recursion with memoization surely avoided some subproblems but we can still improve time complexity using a bottom-up approach and we will also reduce the space complexity to O(N^2).

Complete Algorithm:

• We will initialize a 2-D array ‘DP[N][N]’ with -1, where ‘N’ is the number of rows and columns. Here DP represents the maximum number  of apples two k-length paths can pickup and  two k-length paths arrive at (i, k - i) and (j, k - j),  respectively.
• Set ‘DP[0][0]’ = ‘MATRIX[0][0]’.
• Intialise an integer variable ‘MAXK’ = 2*N -1.
• Run a loop for 1<= ‘k’ <= ‘MAXK’ and do:
  • Run a loop for min(N-1,K)<= ‘i’ <=0  and do:
    • If (k-i) is greater than ‘N’ then do:
      • Continue iterating.
    • Run a loop for min(N-1,K)<= ‘j’ <=0  and do:
      • If (k-j) >= ‘N’ or ‘MATRIX[i][k-1]’ <0 or ‘MATRIX[j][k-j] <0 then do:
        • Set ‘DP[i][j]’ = -1.
      • Intialise an integer variables “COUNT’ = ‘DP[i][j]’.
      • ‘COUNT’ = maximum  of ( ‘DP[i][j-1]’ , ‘DP[i-1][j]’ , ‘DP[i-1][j-1]’ , ‘COUNT’ ) .
      • Set DP[i][j] = ‘COUNT’ + ‘MATRIX[i][k-i]’
      • If i is not equal to j then do:
        • Set DP[i][j] = ‘DP[i][j]’ + ‘MATRIX[j][k-j]’
• Return DP[N-1][N-1].