Maximum-value path through a grid

Question

You're given a grid of payoffs. Starting at the top-left cell and moving only right or down, you must reach the bottom-right cell, collecting the value of every cell you pass through.

grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]]
-> 12          # path 1 -> 3 -> 5 -> 2 -> 1

Return the maximum total collectible. Aim for $O(nm)$ .

Accepted Answer

Let dp[r][c] be the best total for any valid path ending at (r, c). Because the last move into a cell comes from the left or from above, dp[r][c] = 	ext{grid}[r][c] + \max(dp[r-1][c],\; dp[r][c-1]) with the first row/column only having one feasible predecessor. Fill row by row; the answer sits in the bottom-right cell. Greedily taking the bigger neighbor at each step fails, on the example, greedy at (0,0) can be lured down the 4 column and misses the 5. On the example the dp table's bottom row ends 7, 11, 12, answer 12. Time O(nm), space O(nm), reducible to O(m) by keeping only the current r…

Maximum-value path through a grid

Your answer

More Coding questions