You have a square matrix of unsigned integer values. Say, 5 + 5.
Each row of that matrix contains numbers from 1 to 5 (or to whatever length of the matrix), randomly sorted.
You can move through the matrix only one step at the time - either straight down, left-down or right-down.
Your challenge is to write a code that will start at the middle of the top row, and find the path down with the highest sum.
Example:
For the following matrix, you start in c/0. For this matrix the best path would be: c/0
, d/1
, d/2
, e/3
, d/4
which scores 4+4+5+4+5 = 22
.
This challenge comes from peledzohar here on DEV.
Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!
Top comments (2)
My solution in js
So an easy "greedy" implementation isn't going to work for this one since it could easily happen that the best eventual path has the worst first move.
The problem does have a nice optimal substructure though, in that after you make a move, the path from there is the best one from that point, irrespective of what path you took to get to that point.
That points toward using dynamic programming to solve it.
Here's a JS impl: