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!