Collect maximum value of coins in a matrix

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++:

 

Download   Run Code

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*N2) 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.

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Manju
Guest

// 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…?????? 🙁 🙁