Tabulation

Tabulation fills a table from the smallest subproblems up, with a loop instead of recursion. It avoids stack depth limits and often lets you keep only the last few rows.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain how tabulation fills a table from the smallest subproblems up
Convert a memoised recursion into a loop over a table
Spot a loop order that reads cells not yet computed

In practice

A few lines that show Tabulation doing its job.

Python

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for total in range(1, amount + 1):
        for c in coins:
            if c <= total and best[total - c] + 1 < best[total]:
                best[total] = best[total - c] + 1
    return best[amount] if best[amount] != INF else -1

min_coins([1, 5, 6], 11)      # 2 (5 + 6)

The common mistake

Watch for

Filling the table in an order that reads cells not yet computed. The loop order must guarantee every subproblem a cell depends on is already final.

What to know first

Your roadmap puts these before Tabulation, unless you already know them.

Overlapping subproblems

How it stays learned

Once a session shows you understand Tabulation, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Where it leads

Topics that build on Tabulation.

Knapsack patterns

Previous in the module← Overlapping subproblems

Next in the moduleKnapsack patterns →