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:

functiononeStepAtATime(matrix){// For keying an object by coordinateconstgetCoorKey=(x,y)=>`${x}${y}`;// The a/0, d/5 style when displaying coordinatesconstgetDisplayCoorKey=(x,y)=>`${String.fromCharCode('a'.charCodeAt(0)+x)}/${y}`;// A store of the best single block moves found so farconstbestMoveFromCoordinateMemo={}// The dynamic programming function. This finds the best of the three options at each point by recursing into itselfconstbestMoveFromCoordinate=(x,y)=>{// bottom row just early exitsif(y==matrix.length-1)return{sum:matrix[y][x]};constcoorKey=getCoorKey(x,y);// also early exit if we've already memo'd this spotif(bestMoveFromCoordinateMemo[coorKey])returnbestMoveFromCoordinateMemo[coorKey];// This reduce finds the best sum starting from one of the three reachable spots on the next line// the accumulator is an object with `dx` (change in x) and `subsum` propertiesconst{dx,subsum}=[-1,0,1].reduce((bestSubmove,dx)=>{// early exit if we went out of boundsif(x+dx<0||x+dx>=matrix[y+1].length)returnbestSubmove;// destructure `bestSubmove`const{subsum:bestSubsum}=bestSubmove// Recurse to find the best move from hereconst{sum:subsum}=bestMoveFromCoordinate(x+dx,y+1);// accumulate the highest possible sumreturnbestSubsum>subsum?bestSubmove:{dx,subsum};},{subsum:-Infinity});constsum=matrix[y][x]+subsum;returnbestMoveFromCoordinateMemo[coorKey]={dx,sum};}// Present the path from a point for displayconstmovesFromCoordinate=(x,y)=>{if(y>=matrix.length)return[]const{dx}=bestMoveFromCoordinate(x,y);return[getDisplayCoorKey(x,y)].concat(movesFromCoordinate(x+dx,y+1))}// The output of the overall function as a stringreturnmovesFromCoordinate(matrix[0].length>>1,0).join(', ')}console.log(oneStepAtATime([[2,1,4,5,3],[5,2,1,4,3],[1,3,2,5,4],[1,5,2,3,4],[3,2,1,5,4]]))// > c/0, d/1, d/2, e/3, d/4constno=-Infinity;// A "Greedy" solution won't work on this problem// in this case the right path looks good to start with, but ends up being a bad choiceconsole.log(oneStepAtATime([[no,no,1,no,no],[no,1,no,10000,no],[1,no,no,no,100000],[1,no,no,no,1000000],[996,no,no,no,no]]))// > c/0, b/1, a/2, a/3, a/4

## re: Daily Challenge #90 - One Step at a Time VIEW POST

FULL DISCUSSIONSo 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

fromthat point, irrespective of what path you took toget tothat point.That points toward using dynamic programming to solve it.

Here's a JS impl: