Gold Mine Problem

Problem Statement

Given a gold mine of size m × n. Each cell has a certain amount of gold. You can enter from any row in the first column and move to the right (right, right-up diagonal, or right-down diagonal). Find the maximum gold you can collect.

Example:

• Input: mine = [[1, 3, 3], [2, 1, 4], [0, 6, 4]]
• Output: 12 (path: 2 → 1 → 4 starting from row 1, or the path giving max gold)

Noob-Friendly Explanation

Imagine a grid of caves, each with some gold nuggets. You start at any cave on the left side and move rightward. At each step you can go straight right, diagonally up-right, or diagonally down-right. You want to pick the path that collects the most gold. Think of it like a side-scrolling game where you grab coins — you can only move forward and slightly up or down.

Approach 1: Brute Force (Recursion)

Intuition

Start from every cell in the first column. For each cell, try all 3 possible moves (right, right-up, right-down) and pick the path with the most gold.

Algorithm

1. For each row in column 0, start a recursive search
2. At each cell, try moving right, right-up, and right-down
3. Return the maximum gold collected

public class Solution {
    public int maxGold(int[][] mine, int row, int col, int m, int n) {
        // Out of bounds
        if (row < 0 || row >= m || col >= n) return 0;

        // Move right, right-up, right-down
        int right = maxGold(mine, row, col + 1, m, n);
        int rightUp = maxGold(mine, row - 1, col + 1, m, n);
        int rightDown = maxGold(mine, row + 1, col + 1, m, n);

        return mine[row][col] + Math.max(right, Math.max(rightUp, rightDown));
    }

    public int getMaxGold(int[][] mine) {
        int m = mine.length;
        int n = mine[0].length;
        int maxGoldCollected = 0;

        for (int i = 0; i < m; i++) {
            maxGoldCollected = Math.max(maxGoldCollected, maxGold(mine, i, 0, m, n));
        }
        return maxGoldCollected;
    }
}

Complexity Analysis

• Time Complexity: O(3^n) - Each cell branches into 3 paths, depth is n columns
• Space Complexity: O(n) - Recursion stack depth equals number of columns

Approach 2: Optimal (Bottom-Up DP)

Intuition

Process columns from right to left. For each cell, the maximum gold from that cell onward is the cell's gold plus the max of the three reachable cells to the right.

Algorithm

1. Create a DP table same size as mine, copy last column values
2. Process from second-last column to the first
3. For each cell, dp[i][j] = mine[i][j] + max(dp[right], dp[rightUp], dp[rightDown])
4. Answer is the maximum value in the first column of the DP table

public class Solution {
    public int getMaxGold(int[][] mine) {
        int m = mine.length;
        int n = mine[0].length;
        int[][] dp = new int[m][n];

        // Copy last column
        for (int i = 0; i < m; i++) {
            dp[i][n - 1] = mine[i][n - 1];
        }

        // Fill from second-last column to first
        for (int col = n - 2; col >= 0; col--) {
            for (int row = 0; row < m; row++) {
                int right = dp[row][col + 1];
                int rightUp = (row > 0) ? dp[row - 1][col + 1] : 0;
                int rightDown = (row < m - 1) ? dp[row + 1][col + 1] : 0;

                dp[row][col] = mine[row][col]
                             + Math.max(right, Math.max(rightUp, rightDown));
            }
        }

        // Find max in first column
        int result = 0;
        for (int i = 0; i < m; i++) {
            result = Math.max(result, dp[i][0]);
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(m * n) - Visit each cell once
• Space Complexity: O(m * n) - DP table of same size as input