#1219
Path with Maximum Gold
Medium Grid DFS backtracking
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Each grid cell holds some gold (0 means you can't step there). Starting anywhere, walk up/down/left/right without revisiting a cell and collect gold. Return the most gold possible.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: walk through gold cells without revisiting; collect the most gold.
Why this works: try each gold cell as a start, DFS in four directions, and restore the cell when backtracking.
Example: [[0,6,0],[5,8,7],[0,9,0]]
9 → 8 → 7 = 24 (best)✦Hints open one at a time
Try every non-zero cell as a start.
DFS with backtracking: take the gold, mark the cell 0, explore, then put the gold back.
↗Approach
For each start, dfs returns the best total from that cell: its gold plus the best of the four neighbours. Restore the cell after exploring.
</>Solution (Java)
class Solution {
public int getMaximumGold(int[][] grid) {
int best = 0;
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] > 0) best = Math.max(best, dfs(grid, r, c));
return best;
}
private int dfs(int[][] g, int r, int c) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] == 0) return 0;
int gold = g[r][c];
g[r][c] = 0; // mark visited
int more = Math.max(Math.max(dfs(g, r + 1, c), dfs(g, r - 1, c)),
Math.max(dfs(g, r, c + 1), dfs(g, r, c - 1)));
g[r][c] = gold; // backtrack
return gold + more;
}
}!Common mistake
Not restoring the cell's gold, which corrupts later starts.
Complexity
- Time: O(G · 3^G), G = gold cells (at most 25).
- Space: O(G).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon