CODEWITHSUNDEEP
javaalgorithmcomputer-science
Omg I killed Kennny
Omg I killed Kennny

Reputation: 321

Find path on a matrix to get max value

I know, this is an old problem, if given a matrix like：

[1 1 2 3，
 2 3 4 4，
 3 4 1 3，
 2 1 3 4]

Start at a given position, from right to left, only move right or up or down, can not go back in same way and stop at right, find a path to get max value.

I am considering to use DP(May need try all possible path and calculate value), but it seems it will cost a lot of memory since it store all the possible solutions and may also be slow.

I am wondering if there are any other thoughts or ways to make a better solution? A quicker solution if possible?

Upvotes: 0

Views: 151

Answers (2)

Salvador Dali
Salvador Dali

Reputation: 222511

I think that there is a way to do a DP and I just can't quickly find it. Because no one answered it so far I will give a graph method. Create a directed graph where an edge from A to B will be equal to the number in that vertex. It is clear from your description that it will not have any cycles. You will get a grid graph like this, but only directed:

enter image description here

Now get an vertex source which is somewhere on the right and connect it to the first layer (put all the edges equal to 0). The same with a destination, but it is on the left.

Now run longest path in directed acyclic graph

Upvotes: 2

Robert Bräutigam
Robert Bräutigam

Reputation: 7744

If you want to optimize for memory, you might try Backtracking. This would involve only storing the current path, and the path and value for the best solution yet.

Outline is:

  1. You store a list of steps (right, up, down)
  2. You go depth-first so to speak, try to make a new step if you can
  3. If you can't, just go back one and change the step to the next possible direction. (Store this path if it's better than previously stored one).
  4. If there is no next possible direction for the step, repeat 3.
  5. If all possibilities are exhausted, return the stored best path.

Backtracking at wikipedia: https://en.wikipedia.org/wiki/Backtracking

Upvotes: 2

Related Questions