Gold Mine Problem

The problem, simply

A gold mine is a grid with m rows and n columns. Each cell holds some gold. A miner starts in any cell of the first column. From cell (r, c) the miner can step to (r - 1, c + 1) (up-right), (r, c + 1) (right) or (r + 1, c + 1) (down-right), as long as it stays inside the grid. The walk ends at the last column.

Give back the most gold the miner can collect.

A story to remember it

Picture it

Examples

Way 1: the simple way

From a cell, the best total is its own gold plus the best of the three cells it can step to. Ask that with recursion, and try every starting row.

1. Outside the grid, or past the last column: 0 gold.
2. Otherwise: mine[r][c] + max(best(r-1, c+1), best(r, c+1), best(r+1, c+1)).
3. The answer is the largest best(r, 0) over all rows r.

class Solution {
    int best(int[][] mine, int r, int c) {
        int m = mine.length, n = mine[0].length;
        if (r < 0 || r >= m || c >= n) return 0;     // off the map
        int upRight = best(mine, r - 1, c + 1);
        int right = best(mine, r, c + 1);
        int downRight = best(mine, r + 1, c + 1);
        return mine[r][c] + Math.max(right, Math.max(upRight, downRight));
    }

    public int maxGold(int[][] mine) {
        int answer = 0;
        for (int r = 0; r < mine.length; r++) {
            answer = Math.max(answer, best(mine, r, 0));   // try every starting row
        }
        return answer;
    }
}

How long it takes: every cell asks three cells, for n columns, so one start costs up to 3^n, and there are m starts: O(m * 3^n). Extra room: the chain of calls is n long, O(n).

Way 2: the clever way

There are only m * n cells, and best(r, c) is the same every time. Fill a table dp from the last column to the first.

1. Last column: dp[r][n-1] = mine[r][n-1].
2. For c from n - 2 down to 0, for every row r: dp[r][c] = mine[r][c] + max of the up to three cells dp[r-1][c+1], dp[r][c+1], dp[r+1][c+1] that exist.
3. The answer is the largest number in column 0.

class Solution {
    public int maxGold(int[][] mine) {
        int m = mine.length, n = mine[0].length;
        int[][] dp = new int[m][n];                  // dp[r][c]: most gold from (r, c) to the right edge
        for (int r = 0; r < m; r++) dp[r][n - 1] = mine[r][n - 1];
        for (int c = n - 2; c >= 0; c--) {           // right to left
            for (int r = 0; r < m; r++) {
                int right = dp[r][c + 1];
                int upRight = (r > 0) ? dp[r - 1][c + 1] : 0;
                int downRight = (r < m - 1) ? dp[r + 1][c + 1] : 0;
                dp[r][c] = mine[r][c] + Math.max(right, Math.max(upRight, downRight));
            }
        }
        int answer = 0;
        for (int r = 0; r < m; r++) answer = Math.max(answer, dp[r][0]);   // any start row
        return answer;
    }
}

How long it takes: three looks per cell, O(m * n). Extra room: the table, O(m * n). Each column only needs the column to its right, so two columns of size m are enough for O(m).

Watch out for

• Edges of the grid. Row 0 has no up-right step and the last row has no down-right step. Using 0 for them is safe because gold is never negative.
• Filling the wrong way. Left to right also works, but then dp means "most gold to reach this cell", and the answer is the max of the last column. Do not mix the two meanings.
• A one column mine. The loop never runs, and the answer is the biggest single cell.

What interviewers ask next

• Print the walk. Start at the best cell of column 0 and keep stepping to the neighbor with the biggest dp value, as in the last frame above.
• What if cells can be negative (traps)? Then "off the map" must count as impossible, not 0: use a very small number for missing neighbors.
• What if the miner walks top to bottom instead, or can also step left? Top to bottom is the same idea turned sideways (this is the "minimum falling path sum" problem). Stepping left makes loops, so you need a graph search like Dijkstra instead.
• Two miners walk at the same time and gold is only collected once? That is "Cherry Pickup": track both miners together, dp[c][r1][r2].

Remember this

Grown-up words: the sticky notes are the DP table, filling from the end is bottom-up DP, the three steps are the transitions, the repeated cells in the tree are overlapping subproblems, and the walk is a path in a grid.