Gold Mine Problem (Recursion & Dynamic Programming)

Given a gold mine (matrix) M of (n x m) dimensions.

Each field in this mine contains a positive integer which is the amount of gold in tons.

Initially the miner is at first column but can be at any row.

From a given cell, the miner can move:

to the cell diagonally up towards the right (top-right)
to the right (right)
to the cell diagonally down towards the right (bottom-right)

Find out maximum amount of gold which he can collect.

Input: n = 3, m = 3

M = {{1, 3, 3},
     {2, 1, 4},
     {0, 6, 4}};

Output: 12

Input: n = 4, m = 4

M = {{1, 3, 1, 5},
     {2, 2, 4, 1},
     {5, 0, 2, 3},
     {0, 6, 1, 2}};

Output: 16

Solutions

Method 1: Recursion

This "Gold Mine Problem" is a variation of the Matrix Chain Multiplication.

The idea is to start from each row of the first column and return the maximum gold collected.

Recursively check and return the maximum of the available three choices (top-right, right, and bottom-right), plus gold in the current position, while traversing for a path from the first column.

Base Condition: We can not go left of the mine but can move top, right, and down, so return "0" when the mine limit is reached i.e. i == n (bottom), j == m (right) and i < 0 (top).

Complexity

The time complexity of this solution is exponential O(3^n*m).

In addition, O(n*m) auxiliary space was used by the recursion stack.

Method 2: Memoization

The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.

We can see that in each recursive call only the value of "i" and "j" changes, so we can store and reuse the result of a function(..i,j..) call using a "n*m" array.

The array will store a particular state (..i,j..) if we get it the first time.

Now, if we come across the same state (..i,j..) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.