# Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves are up, down, left, right and each position can be visited multiple times but only contributes to your sum once.

Example: for K = 8

7 3 5 9
1 2 0 4
9 4 2 7
7 6 3 2


Optimal route (I think): 0 2 4 9 7 6 3 2 0

First off, of course K has to even (or the problem should state of length at most K). Secondly I was thinking of a solution along the lines of:

opt[i][j][t] = the maximum sum that can be obtained at position (i,j) at time t


The problem with this is that you can't be sure where you can come from. There is no way to (efficiently) know what values you can use to calculate opt[i][j][t]. I could keep the actual path for each position but that would be $$O(nmk^2)$$ memory, which is essentially $$O(n^6)$$ - which is extremely unfeasible. Even the solution itself which is $$O(nmk) = O(n^4)$$ is probably a little too slow. And, in fact, if I have to check each path that would make the complexity as bad as the memory necessary.

Does anyone have any ideas? I would appreciate hints to try to figure it out myself, not actual solutions. Thanks!

• If $K$ is large enough, some positions must be visited more than once. – Apass.Jack Dec 21 '18 at 15:02
• "technically each position can be visited multiple times but only contributes to your sum once". Obviously if K is larger than N*M (I'm not sure by how much, but a constant) then the problem becomes trivial, – figure09 Dec 21 '18 at 15:12
• Construct a graph but make a clone of 0 as 0'. Execute a BFS with enabling revisit but in revisit don't add the cost. – kelalaka Dec 21 '18 at 18:19

Indeed. So do it exhaustively for all feasible paths. That is, work on subproblems where you vary $$t$$ up to $$K$$, and store their results, at least for a little while. It should be possible to discard partial results corresponding to clearly bad solutions, and consume just $$O(t^2)$$ memory to remember the cells we should avoid.
Naively one could access a dense matrix opt by dereferencing opt[i][j]. To access the $$n$$th variant of a matrix with sparse edits applied to it, first probe a mapping to see if edit[(i, j, n)] exists, and if not fall back to dereferencing the dense matrix in the usual way. You may find it convenient to build up a path for the $$n$$th variant as a list of (i, j, value) tuples.
Additionally, we can decompose into the "outbound" and "inbound" sub-problems. Visiting a cell essentially sets that cell to zero, so each candidate outbound path gives rise to a new matrix. In the end the outbound path length will be $$\frac{K}{2}$$ and each new matrix gives rise to another $$\frac{K}{2}$$ inbound problems. The inbound solver would probe a hash map, and would add zero to the reward for any cell appearing in the outbound path.