Can the gold mine problem be solved using divide-and-conquer?

Question

There's a well-known dynamic programming problem that goes by the name of the "gold mine." You have a n x n grid, each cell of which contains a certain value of coins. You begin at the bottom left and can only move right, up, or diagonally up and right. The goal of your algorithm is to determine the path through the mine that maximizes the amount of gold you collect.

An example solution: http://www.ideserve.co.in/learn/gold-mine-problem

Is it possible to solve this problem using a divide-and-conquer approach using O(n) space or less, while still using O(n^2) time?

My first suspicion is that you can divide up the grid into quadrants recursively, find the best path in each of those quadrants, then somehow merge the result in the end to get the best path through the whole thing. Using only O(n) space you can store the paths in each quadrant, since the longest path through each of them is 2n - 2. But in doing that you "forget" about other cells that are worth points that weren't chosen, and the answer provided by that algorithm has the tendency to be incorrect. If we look through all the cells at each merge step in an attempt to remember the discarded ones (which takes n^2 time), then the solution to the recurrence relation for running time becomes n^2 log n instead of n^2, via the master theorem. The merge step has to be done in O(n log n) or O(n).

The space requirement here is the kicker more so than the time requirement.

Answer 1

There's a problem with your divide-and-conquer approach of dividing the grid into four quadrants: The solutions for the quadrants are not independent of each other. And you can't find the optimal solution by combining the locally optimal sub-solutions of each quadrant.

+---+---+
| C | D |
+---+---+
| A | B |
+---+---+

Here, D can be calculated independently. However, the solution for C depends on D, B depends on D, and A depends on B, C, D. (Dependency is determined by reachability.)

Solving the problem for a quadrant does not mean we find the best path. Instead, we have to find the best path for each cell on their left and lower edges, since we do not know where the best path will enter that quadrant.

The exact space complexities depend on what we are trying to calculate:

• the best path: this will take O(n) space per record for a quadrant with n-long edges.
• the value of the best path: this will take O(1) space per record.

I'll sidestep that for this discussion and will denote the space requirement with s(n). Then, the solution of a quadrant requires O(n·s(n)) space for the records of the left and lower edge.

The total space complexity of the algorithm is then given through the recurrence relation T(n) = 4·T(n/4) + O(n · s(n)). This would give T(n) ∈ Θ(n · s(n)) for either choice for s(n).

Writing down the algorithm would be extremely tedious, so I'll not do that here. However, the signature of the recursive solver would be:

solve_quadrant(grid: int[n, n],
               x_start: int, x_end: int,
               y_start: int, y_end: int,
               upper_edge: Result[],
               right_edge: Result[])
               -> (left_edge: Result[], lower_edge: Result[])

And the top-level invocation would be:

solve(grid: int[n, n]) -> Result {
  left_edge, lower_edge = solve_quadrant(grid, 0, n, 0, n, {0, ..., 0}, {0, ..., 0})
  return lower_edge[0] // assuming bottom-left is at coordinate (0, 0)
}

Since the divide-and-conquer algorithm has to satisfy the same data dependencies as a dynamic programming solution, it is unlikely to beat the DP solution with space complexity Θ(n · s(n)). In fact, the complexities of the “divide & conquer” algo and the DP algo are equivalent, since they do the same thing the same way – only the strategy for subdivision is different. However, the DP solution is far easier to program since it doesn't have to consider as many edge conditions.

Answer 2

It turns out there was an answer.

The algorithm to do this works as follows:

Divide up the grid into quadrants. Begin solving the DP values for the top right quadrant, then the top left, then the bottom right. When you're doing this, save only the DP data for the cells that border other quadrants, and get rid of all other working space.

The actual recursion then begins in the bottom left quadrant. This subproblem looks identical to the larger problem - divide up the quadrant in four, and do the same thing again.

When you get down to a grid of size 2x2, solve normally using the DP approach. This is constant time. When you're finished getting the path through that grid, you'll also know what quadrant you're entering next because you've kept the border cells in memory and can make a choice. Now, solve the path through that quadrant, and then the last one.

The path only travels through three quadrants because of the constraints on the moveset. So we're only actually solving three sub-problems, not four. It's because of this that the recurrence still simplifies to O(n^2):

T(n) = 3T(n/2) + O(n^2)

The O(n^2) is the first part of the algorithm, where you're getting the bordering DP cells. The 3T(n/2) is the solving of the three quadrants. This belongs to the case in the Master Theorem where log_b(a) < c, therefore T(n) = O(n^c) = O(n^2).

The recurrence for space is this:

T(n) = T(n / 2) + n

This belongs to the same case in the Master Theorem as the recurrence for the running time. The total space used is O(n).