#1219

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Path with Maximum Gold

Find the path with the maximum gold in a grid with backtracking and pruning techniques to maximize the gold collected.

Problem Statement

You are given a grid representing a gold mine. Each cell in the grid contains an integer indicating the amount of gold it holds, and 0 indicates an empty cell. Your task is to return the maximum amount of gold you can collect under the following conditions: starting from any cell, you can move to adjacent cells (up, down, left, or right), and you cannot visit a cell more than once. If a cell contains 0, you cannot collect gold from it, but it can still be part of your path.

The gold collection should be maximized by exploring all possible paths in the grid. For each valid path, accumulate the gold and find the path that leads to the greatest sum. Since the grid is relatively small (maximum size 15x15), the problem is best tackled using recursion, backtracking, and pruning to avoid inefficient searches in non-optimal paths.

Examples

Example 1

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]

Output: 24

[[0,6,0], [5,8,7], [0,9,0]] Path to get the maximum gold, 9 -> 8 -> 7.

Example 2

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]

Output: 28

[[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]] Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

Solution Approach

Recursive Backtracking

Use a recursive function to explore all possible paths from each non-zero cell, moving to adjacent cells in all directions. At each step, accumulate the amount of gold collected along the way and return the maximum gold collected from that path.

Pruning and Memoization

Implement pruning techniques to stop exploring paths that are not promising, such as when moving outside the grid or revisiting cells. Memoization can also be used to store results for subproblems to avoid redundant calculations.

Boundary and Cell Constraints

Ensure boundary checks are applied to prevent out-of-bounds errors when exploring the grid. Additionally, handle cells with a value of 0 by treating them as obstacles that cannot be traversed.

Complexity Analysis

Metric	Value
Time	O(m \cdot n - g + g \cdot 3^g)
Space	O(g \cdot 3^g)

The time complexity is O(m * n - g + g * 3^g), where m is the number of rows, n is the number of columns, and g is the number of gold-containing cells. The space complexity is O(g * 3^g) due to the recursive call stack and memoization storage for the gold-containing cells.

What Interviewers Usually Probe

The candidate demonstrates clear understanding of backtracking and pruning techniques.
The solution shows efficient handling of recursion and exploration within the problem's constraints.
The candidate applies memoization and pruning to reduce redundant calculations effectively.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle the grid boundaries, which can lead to out-of-bounds errors.
Not properly pruning unpromising paths, leading to inefficient and slower solutions.
Overcomplicating the problem with unnecessary data structures instead of focusing on the core recursive solution.

Follow-up variants

Grid size increases (beyond 15x15), requiring a more optimized approach.
Different traversal constraints (e.g., limiting movement to certain directions).
Alternative ways to handle the grid representation, such as using a dynamic programming approach.

FAQ

How does backtracking help solve the 'Path with Maximum Gold' problem?

Backtracking allows us to explore all possible paths from any starting cell, ensuring that we can find the path with the maximum gold collected. By pruning paths early, we avoid exploring unpromising branches.

What is the time complexity of the solution for 'Path with Maximum Gold'?

The time complexity is O(m * n - g + g * 3^g), where m is the number of rows, n is the number of columns, and g is the number of gold-containing cells.

What should I focus on when solving 'Path with Maximum Gold' in a grid?

Focus on optimizing the recursive backtracking solution, applying pruning to discard unpromising paths early, and ensuring you correctly handle the grid boundaries and cells with zero gold.

Can this problem be solved with dynamic programming?

Yes, dynamic programming can be used to store intermediate results, but backtracking with pruning is more intuitive and efficient for this problem given the grid size constraints.

What happens if I don't use pruning in my backtracking solution?

Without pruning, your solution may explore many unnecessary paths, leading to inefficiencies and a longer runtime. Pruning ensures that only promising paths are explored.

terminal

Solution

Solution 1: DFS

We can enumerate each cell as the starting point, and then start a depth-first search from the starting point. During the search process, whenever we encounter a non-zero cell, we turn it into zero and continue the search. When we can no longer continue the search, we calculate the total amount of gold in the current path, then turn the current cell back into a non-zero cell, thus performing backtracking.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            if not (0 <= i < m and 0 <= j < n and grid[i][j]):
                return 0
            v = grid[i][j]
            grid[i][j] = 0
            ans = max(dfs(i + a, j + b) for a, b in pairwise(dirs)) + v
            grid[i][j] = v
            return ans

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        return max(dfs(i, j) for i in range(m) for j in range(n))

Continue Practicing

#980 unique paths iii #773 sliding puzzle #1222 queens that can attack the king