Quiz
Warm-up from lesson 9-1: before writing any DP you state two sentences. What are they?
2-D DP: grid paths
Unit 9's tables tracked histories that unroll along one line. Plenty of real problems live on two axes — comparing two strings (the edit-distance behind spell-check and DNA alignment), matching two sequences, moving across a board — and their tables simply gain a second index. Grid paths is the cleanest first specimen of that jump.
A robot starts at the top-left of an r×c grid and only moves right or down. How many distinct routes reach the bottom-right?
Meaning: table[r][c] = number of routes reaching cell (r, c). Recurrence: the last move into a cell came from above or from the left, so:
table[r][c] = table[r-1][c] + table[r][c-1]
Base cases: everything in the top row and left column is 1 (only one straight route hugs an edge).
Same recipe as climbing stairs in lesson 9-1, one dimension up: fill row by row, and every ingredient is already computed when you need it. Time O(r·c), one table cell each.
Code exercise · python
Run this. The printed rows should match the figure exactly, ending with 10 routes across a 3×4 grid.
Code exercise · python
Your turn. Now each cell has a cost and you want the CHEAPEST right/down path from top-left to bottom-right. table[r][c] = grid[r][c] + min(best from above, best from left). Mind the edges: the top row can only come from the left, the left column only from above.
Quiz
unique_paths on a 100×100 grid: how many table cells does the DP fill, and what would recursion WITHOUT a memo do instead?