Maximum bounty from two paths through a rectangular grid

Question

I am trying to solve problem similar to this problem at GeeksforGeeks, yet different:
Given a rectangular 2-d grid with some coin value present in each cell, the task is to start from the top-left and bottom-right corner going right or down, and from bottom-right to top-left going left or up, maximizing the combined amount of coin picked. Coin in each cell can be picked only once.
The solution in the link is to start both traversal simultaneously but that's not going to work here.
How should I solve this? The brute force way of doing this would be enumerating all paths and picking two paths that maximizes the sum of coins picked but that's not going to work for large input.

Answer 1

We can solve this problem by making three observations:

• First, rather than starting at two different points, we can reverse the direction of the second person, so the problem become two people start at the top left corner and move toward bottom right corner simultaneously.

• Second, if we make an assumption that, two persons will make their move at the same speed, the state of these two can be represented by only three parameters: x1, x2 and y1. As we can easily calculate the number of move the first person had made based on his current location (sum x1 + y1, as he can only move right or down), so, we can also figure out the current location of second person (y2 = x1 + y1 - x2). Keep in mind that, both need to make same number of step to reach the bottom right, so both will have same number of move in any given time.

• Lastly, We should notice that, a person cannot visit a location more than one, as the only directions each can take are right or down. Further more, in any state, the number of move each person made are equaled, so, if there exists location(s) visited by both persons, they will visit this location at the same time (and only when x1 = x2), thus, we can easily count the number of coins collected.

From these observations, it can be easily reduced to a similar problem to the problem in OP's link:

Starting from state (x1, x2, y1), as each person can only move right or down, we will have following next states:

 (x1 + 1, x2 + 1, y1) : Both move to the right.
 (x1 + 1, x2, y1) : First person move right, second move down
 (x1, x2 + 1, y1 + 1) : First move down, second move right
 (x1, x2, y1 + 1) : Both move down.

So, we have our dynamic programming formula:

dp[x1][x2][y1] = coin[x1][y1] + (x2 != x1 ? coin[x2][y2] : 0 ) + max(dp[x1 + 1][x2 + 1][y1], dp[x1 + 1][x2][y1], dp[x1][x2 + 1][y1 + 1], dp[x1][x2][y1 + 1])