Chocolate Pickup

Approach: Say Alice is at column 'C1' and Bob is at column 'C2' of row 'R'. We will try all possible ways of moving both of them to the next row 'R' + 1 under the given conditions.

 

Each person has three choices in the next row, so combined, they have 3 * 3 = 9 choices. Among these nine choices, we will consider the path which gives us the maximum score. In case both of them land on the same cell in a row, we will add that cell's value only once.

 

We will implement the above logic recursively.

 

Algorithm : 

1. We will pass the ‘currRow’ as 0 as both are on the starting point and ‘C1’ as 0 and ‘C2’ as ‘C’ - 1 as coordinates of Alice and Bob respectively.
2. Return 'getMaximumChocolates(0, 0, C - 1, grid)’.

maximumChocolatesHelper(currRow, C1, C2, GRID):

1. Check if current coordinates 'currRow', 'C1', and 'C2' are valid or not. If they are not valid, then return 0.
2. Declare and Initialize variable 'maximumChocolates' with 0.
3. Run a loop from -1 to 1 with variable 'i' and another nested loop from -1 to 1 with variable 'j'.
4. Update 'maximumChocolates' with the maximum of it and 'maximumChocolatesHelper(currRow + 1, C1 + i, C2 + j, GRID)'
5. If ‘C1!=C2’ then add ‘grid[r][c2]’ to the ‘maximumChocolates’.
6. Return '(maximumChocolates + grid[r][c1])’.

Approach: In the first recursive brute force approach, there are repeated calculations due to overlapping paths. We will use memoization to speed things up.

 

We will use dynamic programming, and 'dp[R][C1][C2]' will maintain the maximum total score that both robots can accumulate till the end when starting from columns 'C1' and 'C2' of row 'R'.

 

We will optimize it more by skipping 'C1' > 'C2' paths because scores of those paths would already be counted in symmetrical 'C1' < 'C2' paths. 

 

Algorithm : 

1. Initialize one 3D ‘DP’ array with all values -1.
2. We will pass the ‘currRow’ as 0 as both are on the starting point and ‘C1’ as 0 and ‘C2’ as ‘C’ - 1 as coordinates of Alice and Bob respectively.
3. Return 'getMaximumChocolates(0, 0, C - 1, grid, dp)’.

maximumChocolatesHelper(currRow, C1, C2, grid, DP):

1. Check if current coordinates 'currRow', 'C1', and 'C2' are valid or not. If they are not valid, then return 0.
2. If ‘DP[currRow][C1][C2]’ is not -1 then return it’s value.
3. Declare and Initialize variable 'maximumChocolates' with 0.
4. Run a loop from -1 to 1 with variable 'i' and another nested loop from -1 to 1 with variable 'j'.
5. Update 'maximumChocolates' with the maximum of it and 'maximumChocolatesHelper(currRow + 1, C1 + i, C2 + j, grid)'
6. If ‘C1!=C2’ then add ‘grid[r][c2]’ to the ‘maximumChocolates’.
7. Return ‘DP[currRow][C1][C2]’ = '(maximumChocolates + grid[r][c1]).

Approach:

We can also solve this problem using iterative dynamic programming. The approach is similar to the recursive approach with a slight change. We will start from the base conditions instead of the other way around. The idea is to keep only the previous row dp array in memory and construct the current row dp array thanks to it. Then when the current loop is finished, we just have to assign the previous row dp array to be the current row dp array.

Algorithm : 

1. Initialize the 2D vector 'prev_dp' of size 'C^2'
2. Run a loop from 0 to 'R' with variable 'row'
   • Initialize a  2D vector 'current_dp' of size 'C^2'
   • Run a loop from 0 to 'min(c, row + 1) with variable 'C1'
     • Run a nested loop from 0 to 'max(0, c - 1 - row)' with variable 'C2'
       • Initialize a variable 'prev_max' with 0.
       • Run a loop from 'max(0, c1 - 1)' to 'min(c - 1, c1 + 1)' with variable 'offset1'
         • Run a nested loop from 'max(0, c2 - 1)' to 'min(c - 1, c2 + 1)' with variable 'offset2'
           • Update 'prev_max' with 'max(prev_max, prev_dp[offset1][offset2])'
       • If ‘C1’ == 'C2' then update 'current_dp[c1][c2]' with 'prev_max + grid[row][c1]'
       • Else update 'current_dp[c1][c2]' with 'prev_max + grid[row][c1] + grid[row][c2]'
3. Initialize a variable 'res' by 0
4. Run a loop from 0 to 'C' with variable 'i' and run a nested loop from 0 to 'C' with variable 'j'
   • Update 'res' with 'max(res, prev_dp[i][j])'
5. Return 'res'