Maximum Coins

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

Approach:  

1. We will use recursion and define a helper function having parameters (MAT, ROW_NO, COL_NO1, COL_NO2, N, M), where ROW_NO is the row number at which Alice and Bob will present, COL_NO1 is the column number of Alice and COL_NO2 is the column number of Bob.
2. From the function, initially we will call helper function which will take parameters (MAT, 0, 0, M-1, N, M), as initially Alice will be at (0,0) hence ROW_NO and COL_NO1 will be 0, and Bob will be at (0, M-1) hence COL_NO2 will be M-1.
3. In helper function, firstly, we will check for the valid condition as no coordinates should get out of matrix dimensions.
4. Then we will check whether we have reached the last row of the matrix , if we have then we should check whether both coordinates are at the end then we return the coins otherwise we should return minus infinity.
5. Initialise the variable coins by minus infinity.
6. Recur for all possible ways:
   1. (i, x) -> (i+1, x-1) or (i+1, x) or (i+1, x+1)
   2. (i, y) -> (i+1, y-1) or (i+1, y) or (i+1, y+1)
7. Update the variable coins by the maximum value that is returned by recursion calls.
8. Final answer would be MAT[i][x] + MAT[i][y] + COINS, if x is not equal to y, otherwise the final answer would be MAT[i][x] + COINS.
9. Return the final answer.

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

Approach:  

1. We will use recursion and memoization and define a helper function having parameters (MAT, DP, ROW_NO, COL_NO1, COL_NO2, N, M), where rowNo is the row number at which Alice and Bob will present, COL_NO1 is the column number of Alice and COL_NO2 is the column number of Bob and DP is the three-dimensional array of dimensions N*M*M initialised with -1.
2. From the function, initially, we will call helper function which will take parameters (MAT, DP, 0, 0, M-1, N, M), as initially Alice will be at (0,0) hence ROW_NO and COL_NO1 will be 0, and Bob will be at (0, M-1) hence COL_NO2 will be M-1.
3. In the helper function, firstly, we will check for the valid condition as no coordinates should get out of matrix dimensions.
4. Then we will check whether we have reached the last row of the matrix, if we have then we should check whether both coordinates are at the final position, then we return the coins otherwise we should return the minus infinity.
5. Check if the value is already calculated or not, if it is already calculated then return the value from the DP array.
6. Otherwise, Initialise the variable coins by minus infinity.
7. Recur for all possible ways:
   1. (i, x) -> (i+1, x-1) or (i+1, x) or (i+1, x+1)
   2. (i, y) -> (i+1, y-1) or (i+1, y) or (i+1, y+1)
8. Update the variable coins by the maximum value that is returned by recursion calls.
9. Final answer would be MAT[i][x] + MAT[i][y] + COINS, if x is not equal to y, otherwise the final answer would be MAT[i][x] + COINS.
10. Save the final answer in the DP array and return the final answer.

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, the row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

Approach:  

1. Create a 3d DP array of dimensions N*M*M, where DP[i][j][k] will denote the maximum coins Alice and Bob can collect when Alice reaches at MAT[i][j] and Bob reaches at MAT[i][k]. It will contain minus infinity when the state is not reachable.
2. For 0th row, Alice and Bob have only one reachable state i.e MAT[0][0] for Alice and MAT[0][M-1] for Bob, thus fill the base conditions (dp[0]) as follows:
   • Fill the DP[0] array by running a nested loop. Check if j is 0 and K is M-1 then the state is reachable check If there is only one column then DP[0][j][k] would be MAT[j][k], else DP[0][j][k] would be summation of MAT[0][j] + MAT[0][k].
   • Otherwise, the current state is not reachable, thus fill DP[0][j][k] as minus infinity.
3. Fill the rest of the DP array.
   • For any state DP[i][j][k], it will be the maximum of the following 9 cases.
     • COINS = MAX(DP[i-1][j-1][k-1], DP[i-1][j-1][k], DP[i-1][j-1][k+1], DP[i-1][j][k-1], DP[i-1][j][k], DP[i-1][j][k+1], DP[i-1][j+1][k-1], DP[i-1][j+1][k], DP[i-1][j+1][k+1])
4. Now DP[i][j][k] would depend on the condition that if j is equal to k then both Alice and Bob will be at the same cell, then
   • DP[i][j][k] = COINS + MAT[i][j].
   • Otherwise , DP[i][j][k] = MAT[i][j] + MAT[i][k] + COINS.
5. Finally, our answer would be DP[N-1][0][M-1]. The final destination of Alice and Bob are (N-1, 0) and (N-1, M-1) respectively.

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, the row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

Approach:  

Since maximum coins that are collected at any row ith will only depend on the number of coins that are collected at (i-1)th row, thus instead of using 3d array of size N*M*M we will use two 3d arrays of size 2*M*M with two variables (CURR and PREV) where to curr will store the answer of the ith row and PREV will store the answer of (i-1)th row, Now, if we will be at (i+1)th row then CURR array will become PREV array.

1. Create an array DP of dimensions 2*M*M, where DP[CURR][j][k] will denote the maximum coins Alice and Bob can collect when Alice reaches the jth column and Bob reaches the kth column. It will contain minus infinity when the state is not reachable.
2. We will have two variables CURR initialized with 0 and PREV initialized with 1 to denote the previous row and current row.
3. For the 0th row, Alice and Bob have only one reachable state i.e MAT[0][0] for Alice and MAT[0][M-1] for Bob, thus fill the base conditions as follows:
   • Fill the DP[CURR] array by running a nested loop. Check if j is 0 and K is M-1 then the state is reachable check If there is only one column then DP[CURR][j][k] would be MAT[j][k], else DP[CURR][j][k] would be summation of MAT[0][j] + MAT[0][k].
   • Otherwise, the current state is not reachable, thus fill DP[CURR][j][k] as minus infinity.
4. After the Base case for the next row, we will flip curr and prev
   • CURR = CURR^1
   • PREV = PREV^1
5. Now for the rest of the row from 1 to N-1.
   • For any state DP[CURR][j][k], it will be the maximum of the following 9 cases.
     • COINS = MAX(DP[PREV][j-1][k-1], DP[PREV][j-1][k], DP[PREV][j-1][k+1], DP[PREV][j][k-1], DP[PREV][j][k], DP[PREV][j][k+1], DP[PREV][j+1][k-1], DP[PREV][j+1][k], DP[PREV][j+1][k+1])
6. Now DP[CURR][j][k] would depend on the condition that if j is equal to k then both Alice and Bob will be at the same cell, then
   • DP[CURR][j][k] = COINS + MAT[i][j].
   • Otherwise , DP[CURR][j][k] = MAT[i][j] + MAT[i][k] + COINS.
7. After we have traversed all the rows, our answer would be CURR[0][M-1]. The final destination of Alice and Bob are (N-1, 0) and (N-1, M-1) respectively.