find path cross matrix with max sum forward then backward

Question

If I have a matrix, every element of the matrix is a non-negative number. I want to walk through the matrix from left-bottom corner to the right-top corner. In every step I can only move upward or rightward, and every visited element will be set to 0; after that, I walk back from the right-top corner to the left-bottom corner, every step I can only move downward or leftward.

My question is how to efficiently find a path with max sum.

Answer 1

Let's have a matrix with N rows and M columns and assume that N>=2 and M>=2, otherwise the solution is trivial. I have an algorithm running in O(max(M,N) * min(N,M)^4) using dynamic programming.

First, let's prove that an optimal solution where the paths don't cross (except at start and end) always exists. We will take any solution and transform in into a non-crossing one without lowering the optimization function.

Proof:

Start by ensuring that the second path (from top-right to bottom-left) is always above or at the same row as the first path. Do that by taking a single section of both path where this isn't true, and swap them. Illustration:

Then, remove one collision at a time. You can always find a collision such that at least one route is turning there, and you can change that path to avoid the collision. Repeat this until all collisions are removed. Illustration of one step:

We see that not only no elements we removed from both paths combined, but more elements have been added, and all elements are non-negative, so the sum could only go up.

The algorithm:

We will only consider paths that don't cross, also I'll assume that N<=M (the matrix wide at least as height). Often we will add number from one column, that can be done quickly using Prefix sum.

We will start at the first column. For each pair (i,j) such that 1<=i<j<=N we will compute the score of that pair, that is the sum of how much can both paths cover starting at (1,1) and ending at (1,i) and (1,j) respectively. Example:

Matrix:
1 2 3
4 5 6
7 8 9

score(1,1) = 7
score(1,3) = 12
score(2,3) = -inf (paths cannot cross)

Then we will compute score of each pair in the next column from the score of pairs in current column. For each pair in the next column, simply look at all the pairs in the previous column whose path can be extended to match the path of current column.

Finally, your answer is the score of pair (N-1, N) in the last column. I apologise for I am terrible at explaining algorithms over written media, I hope it's not completely un-understable.