Know this before you start: “Fill a table bottom-up from small cases”

Bottom-up DP: filling a table

Start from the smallest cases and fill the table in an order where everything you need is already there. No recursion, and often less memory.

The idea

Bottom-up DP is the same recurrence as memoization, computed from small to large in a loop. Write the base cases into the table, then fill each entry from entries already computed.

For grids and two strings, the table is 2-D: dp[r][c] comes from its neighbours above and to the left, so filling row by row works.

When an entry only looks back a row or a couple of steps, keep just those and drop the rest of the table.

See it step by step

Paths in a 3 × 3 grid moving only right or down

First row and column: 1 way each.
dp[1][1] = above + left = 1 + 1 = 2, dp[1][2] = 1 + 2 = 3
dp[2][1] = 2 + 1 = 3, dp[2][2] = 3 + 3 = 6 paths.

In code (Python)

def unique_paths(rows, cols):
    dp = [[1] * cols for _ in range(rows)]      # first row / column: 1 way
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[-1][-1]

def unique_paths_one_row(rows, cols):
    row = [1] * cols
    for _ in range(1, rows):
        for c in range(1, cols):
            row[c] += row[c - 1]                 # above + left
    return row[-1]

print(unique_paths(3, 3), unique_paths(3, 7))   # 6 28
print(unique_paths_one_row(3, 7))               # 28

O(number of cells) time; O(cells), or one row with the space trick.

When you'll use it

Grids, two strings (edit distance, LCS), knapsack, any DP where recursion would be too deep.

Common mistakes

[[0] * cols] * rows, which repeats the same row object.
Filling in an order where needed entries aren't ready yet.