2D Dynamic Programming
A frog must cross an grid from to , moving one cell right or down.
Each cell holds coins. Find the maximum total the frog can collect, including the start and finish.
Dynamic Programming with Path Restoring (DP with Path Restoring)
Instead of checking every path, ask:
What is the most we can collect from this cell to the finish?
This total includes the current cell’s coins. We solve backward from the finish; the frog still moves right or down.
Assume the right and lower neighbors are solved.
Red: move right, then follow the neighbor’s best route:
Blue: move down, then follow the neighbor’s best route:
We keep the larger total:
Current cell → one new move → the neighbor’s best saved continuation.
Reuse the saved result. Any worse continuation can be replaced by the best one without changing our first move.
Use the same grid as the visual:
| Column 1 | Column 2 | Column 3 | Column 4 | Column 5 | |
|---|---|---|---|---|---|
| Row 1 | 2 | 7 | 1 | 4 | 3 |
| Row 2 | 3 | 2 | 9 | 1 | 6 |
| Row 3 | 4 | 8 | 2 | 7 | 2 |
| Row 4 | 1 | 3 | 6 | 2 | 5 |
Cell has 3 coins. Its neighbors store to the right and below.
| Choice | Complete route | Total coins |
|---|---|---|
| Red: right | ||
| Blue: down |
Choose down:
We compare 27 and 28, not just the 2 and 4 coins in the next cells. Each saved total includes that neighbor's best route to the finish.
Compare whole routes, not just the next cell.
To show one optimal route, save a pointer to the chosen neighbor alongside the best total. In a tie, either choice works.
At the finish, collect its coins and stop:
The last row can only go right; the last column can only go down.
Fill the remaining cells bottom to top, right to left, so both neighbors are ready.
The code uses zero-based indices and expects a non-empty rectangular grid.
Our example gives 36 coins. One optimal route collects .
There are cells, each with at most two choices: time and memory.
def maximum_coins(coins):
n, m = len(coins), len(coins[0])
dp = [[0] * m for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
if i == n - 1 and j == m - 1:
# Finish: collect its coins, then stop.
dp[i][j] = coins[i][j]
elif i == n - 1:
# Last row: only right is possible.
dp[i][j] = coins[i][j] + dp[i][j + 1]
elif j == m - 1:
# Last column: only down is possible.
dp[i][j] = coins[i][j] + dp[i + 1][j]
else:
right = dp[i][j + 1]
down = dp[i + 1][j]
dp[i][j] = coins[i][j] + max(right, down)
return dp[0][0]