Given a M x N matrix where each cell contains a coin of some denomination, collect maximum value of coins by traversing the grid.

The first traversal starts from the top-left corner of the matrix and end at the bottom-left corner and the second traversal starts from the top-right corner and end at the bottom-right corner. From any cell `(i, j)` in the matrix, we are allowed to move to cell `(i+1, j+1)` or `(i+1, j-1)` or `(i+1, j)`. If both traversals passes through a same cell, only one can collect coin of that cell.

For example,

**Input: **The given matrix is

[ 0 2 4 1 ]

[ 4 8 3 7 ]

[ 2 3 6 2 ]

[ 9 7 8 3 ]

[ 1 5 9 4 ]

**Output:**The maximum coins collected is 47 (Red coins + Blue coins)

The idea is to simultaneously start the both traversals from the top-left corner `(0, 0)` and the top-right corner `(0, N-1)` of the matrix respectively. For each step, row number would increase by one and the column number might remain the same or can increase/decrease by 1. i.e. `(i, j) -> (i+1, j-1) or (i+1, j) or (i+1, j+1)`.

We collect the coins as move along, and return the maximum possible collection. The recursive algorithm can be implemented as follows in C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <stdio.h> #include <limits.h> #define M 5 #define N 4 // Function to return maximum of two numbers int max(int i, int j) { return (i > j)? i: j; } // Function to check whether (i, x) and (i, y) are valid matrix coordinates int isValid(int i, int x, int y) { return i < M && x >= 0 && x < N && y >= 0 && y < N; } // Collect maximum coins from cell (i, x) to cell (M-1, 0) and from // cell (i, y) to cell (M-1, N-1) int maxCoins(int mat[M][N], int i, int x, int y) { // return if either (i, x) or (i, y) is invalid if (!isValid(i, x, y)) { return INT_MIN; } // current row is the last row if (i == M - 1) { // destination reached if (x == 0 && y == N - 1) { return (x == y) ? mat[i][x] : mat[i][x] + mat[i][y]; } // destination not reached return INT_MIN; } // stores the max number of coins int coins = INT_MIN; // recur for all possible ways: // (i, x) -> (i+1, x-1) or (i+1, x) or (i+1, x+1) // (i, y) -> (i+1, y-1) or (i+1, y) or (i+1, y+1) coins = max(coins, maxCoins(mat, i + 1, x - 1, y - 1)); coins = max(coins, maxCoins(mat, i + 1, x - 1, y)); coins = max(coins, maxCoins(mat, i + 1, x - 1, y + 1)); coins = max(coins, maxCoins(mat, i + 1, x, y - 1)); coins = max(coins, maxCoins(mat, i + 1, x, y)); coins = max(coins, maxCoins(mat, i + 1, x, y + 1)); coins = max(coins, maxCoins(mat, i + 1, x + 1, y - 1)); coins = max(coins, maxCoins(mat, i + 1, x + 1, y)); coins = max(coins, maxCoins(mat, i + 1, x + 1, y + 1)); // update max number of coins with current cell coins before returning if (x == y) return mat[i][x] + coins; else return (mat[i][x] + mat[i][y]) + coins; } // main function int main(void) { int mat[][N] = { { 0, 2, 4, 1 }, { 4, 8, 3, 7 }, { 2, 3, 6, 2 }, { 9, 7, 8, 3 }, { 1, 5, 9, 4 } }; // start with the cells (0, 0) and (0, N-1) printf("The maximum coins collected is %d", maxCoins(mat, 0, 0, N - 1)); return 0; } |

`Output:`

The maximum coins collected is 47

The time complexity of above solution is exponential since it re-computes the same sub-problems again and again. We can easily optimize the code to run in `O(M*N ^{2})` time with Dynamic Programming. The idea is to store the results of function calls and return the cached result when the same input occurs again. The dynamic programming solution is left as an exercise to the readers.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

// destination reached

if (x == 0 && y == N – 1) {

return (x == y) ? mat[i][x] : mat[i][x] + mat[i][y];

}

I did not get this code…?????? 🙁 🙁

Thanks for sharing your concerns.

The inner if condition (x==y) is placed to handle the condition when the matrix has only single column. For that case, we need to collect the coin of last cell only once. Hope you’re clear now.