306. Gold Mine Problem

Given a grid where each cell holds an amount of gold, a miner starts in any row of the leftmost column and repeatedly moves to the cell diagonally up-right, directly right, or diagonally down-right, until falling off the right edge. Find the maximum total gold collectible over any such path.

Input: The first line contains rows and cols. Each of the next rows lines contains cols space-separated integers (gold amounts) forming the grid. Output: Print a single integer - the maximum total gold collectible from any valid path.

1 <= rows, cols <= 500

The starting row isn't fixed - checking the MAXIMUM across the entire leftmost column (not just row 0) is essential, since the miner can enter from any row.

Starting from any row in the leftmost column, collect the maximum gold moving only right, diagonally up-right, or diagonally down-right. Brute force: Try every possible starting row and every possible path from there directly - this branches combinatorially at every column, impractical for large grids. Optimised: Working from right to left, each cell's best achievable gold only depends on the best achievable gold of the (at most 3) cells one column to its right - already computed exactly once each, avoiding any re-exploration of overlapping path suffixes.

Process the grid column by column from right to left (or symmetrically left to right), computing for each cell the best total gold obtainable starting there as its own value plus the maximum of the three reachable cells in the already-computed adjacent column. Because each column's values only depend on the immediately preceding column, only two columns need to be kept in memory at a time instead of the entire table, and the final answer is the maximum value in the leftmost computed column. Time: O(rows*cols) Space: O(rows)

From every cell in the leftmost column, recursively explore all three allowed moves (diagonally up-right, straight right, diagonally down-right) at every step, accumulating the gold collected, until the path falls off the right edge of the grid, and take the maximum total gold seen across all fully explored paths from all starting cells. Because the same (row, col) cell can be reached via many different move sequences and each gets fully re-explored, this repeats enormous amounts of work. Time: O(3^cols) per starting row, exponential overall Space: O(cols) recursion depth

Use the same recursive exploration of the three moves from each cell, but cache the best achievable gold total starting from each (row, col) cell the first time it's computed, returning the cached value on any subsequent call to the same cell. Since there are only rows*cols distinct cells and each is computed once from its already-solved neighbors to the right, the exponential path explosion collapses to work proportional to the grid size. Time: O(rows*cols) Space: O(rows*cols)

1. Work COLUMN BY COLUMN from RIGHT TO LEFT: dp[i][j] = grid[i][j] + the best of dp[i-1][j+1], dp[i][j+1], dp[i+1][j+1] (treating any row outside the grid as contributing 0). 2. Process the LAST column first (its dp value is just the grid value, since there's nowhere further right to go), so every column to its left can look one column ahead. 3. The answer is the MAXIMUM value in the LEFTMOST column of the dp table, since the miner may start in any row.

Time: O(rows*cols) - filling the DP table, one cell at a time. Space: O(rows*cols) for the full table (reducible to O(rows) with a rolling 1D array, processing one column at a time).

Test a grid with a single column (the answer is just the largest value in that column), a single row, and rows = cols = 500 (upper bound) for the column-by-column DP's performance.

Be ready to explain why processing RIGHT TO LEFT (rather than left to right) makes sense here - since movement is always rightward, a cell's best value depends on cells to its right, which must therefore be computed FIRST.