2-D DP: grid paths

The two sentences are what table[i] means in words, and the recurrence, with base cases, that builds it from earlier entries.

Meaning first, recurrence second, and in that order. The recurrence is usually easy once the meaning is precise, and impossible while it is vague.

Today the only change is that the table gains a dimension, table[r][c] instead of table[i].

The meaning sentence gains a clause to match, describing what both indices refer to, and the recurrence gains a term for each way of arriving.

The discipline is otherwise identical, and the two-sentence habit is what makes 2-D DP feel like the same work rather than a new topic.

2-D DP: grid paths

Unit 9's tables tracked histories that unroll along one line. Plenty of real problems live on two axes instead.

Comparing two strings is the big one, since it is the edit distance behind spell-check and DNA alignment. Matching two sequences and moving across a board are the same shape, 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 moves only right or down, so how many distinct routes reach the bottom-right?

Meaning: table[r][c] is the number of routes reaching cell (r, c).

Recurrence: the last move into a cell came from above or from the left, and those two cases cover everything without overlapping, so

table[r][c] = table[r−1][c] + table[r][c−1]

Base cases are that everything in the top row and left column is 1, since 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, for O(r·c) time and one visit per cell.

unique_paths

The printed rows match the figure.

def unique_paths(rows, cols):
    table = [[1] * cols for _ in range(rows)]
    for r in range(1, rows):
        for c in range(1, cols):
            table[r][c] = table[r - 1][c] + table[r][c - 1]
    for row in table:
        print(row)
    return table[-1][-1]

print(unique_paths(3, 4))

Output

[1, 1, 1, 1]
[1, 2, 3, 4]
[1, 3, 6, 10]
10

Initializing every cell to 1 handles both base cases in one line, since the loops start at index 1 and never overwrite the top row or left column.

The list comprehension is required rather than stylistic. [[1] * cols] * rows would make rows references to one shared list, so writing to one row would change all of them.

Both loops start at 1 because row 0 has nothing above it and column 0 has nothing to its left. Reading table[-1][c] in Python would silently wrap to the last row.

The rows are Pascal's triangle laid on its side, which is the clue that a closed-form binomial coefficient also answers this. The DP is what generalizes when the grid has obstacles.

table[-1][-1] reads the bottom-right corner, and the answer for a 3×4 grid is 10 routes.

min_path_sum

Each cell has a cost now, and the goal is the cheapest right-or-down path.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    table = [[0] * cols for _ in range(rows)]
    table[0][0] = grid[0][0]
    for c in range(1, cols):
        table[0][c] = table[0][c - 1] + grid[0][c]
    for r in range(1, rows):
        table[r][0] = table[r - 1][0] + grid[r][0]
    for r in range(1, rows):
        for c in range(1, cols):
            table[r][c] = grid[r][c] + min(table[r - 1][c], table[r][c - 1])
    return table[-1][-1]

print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
print(min_path_sum([[1, 2], [3, 4]]))

Output

7
7

table[r][c] means the cheapest total cost to reach that cell, including the cell's own cost, which is why the recurrence adds grid[r][c] outside the min.

Counting used + and optimizing uses min, exactly like lesson 9-1's shift from climb_table to min_cost_climb.

The edge cells need their own loops here, unlike unique_paths. The top row can only be entered from the left and the left column only from above, so they have one option rather than two.

Filling them first is a correctness requirement, not an optimization. Skipping it would leave zeros in place, and min would read a zero as a free route rather than as an unvisited cell.

The cheap route through the first grid is 1 → 3 → 1 → 1 → 1 = 7, along the top and then down the right edge, and the 5 in the middle is what makes the direct diagonal-ish route worse.

The second grid ties at 7 both ways, since 1 + 2 + 4 and 1 + 3 + 4 are equal, and the min picks one without caring which.

The DP fills 10,000 cells, and recursion without a memo would re-explore an astronomically large tree of paths.

The table is 100 × 100, each cell doing O(1) work, so the whole thing finishes in milliseconds.

Plain recursion would walk every route separately, and the route count is the value that ends up in the corner. For a 100 × 100 grid that number has more than 50 digits.

The gap is not a constant factor, it is the difference between a table and a tree. DP costs the size of the table, and recursion without memory costs the number of paths through it.

Same lesson as unit 5, now in two dimensions. Memoizing the recursion would also give 10,000 subproblems, since top-down and bottom-up solve the identical set.

The space is 10,000 cells too, and it can be cut to one row of 100. Each cell only needs the row above and the cell to its left, which is the 2-D version of lesson 9-1's two-variable trick.