0
Challenge · 65Dynamic Programming

Grid DP

DPused in ~85% of apps

The easiest DP to see, because the table is the same shape as the problem. Each cell asks the same short question: of the few cells I could have arrived from, which was best? Fill the grid once and the answer is waiting in the corner.

Core idea. Make a table the same shape as the grid, where each cell holds the best answer for reaching that cell. Fill it in an order that means the cells you read are already final, which for right and down movement is simply row by row, left to right.
Playground, this isn't a screenshot
filling the grid, one cell at a time
the costs
1
3
1
1
5
1
4
2
1
best cost to reach each cell
1
the corner has no choice, so it is just its own cost
step 1 of 10

Each cell reads only the one above and the one to the left, which is why filling row by row always finds them ready.

↑ play a little first, then dig in