Skip to content
Tutorials Center
My learning

Topics

Lesson 149 of 225 ยท Dynamic Programming

Memoization vs Tabulation

Compare top-down memoization and bottom-up tabulation in Python with one worked problem, a state-definition recipe, space optimization and recursion limits.

The previous lesson showed that dynamic programming means solving each distinct subproblem once. There are two standard ways to organise that work. Memoization is top-down: write the natural recursive solution, then cache the results. Tabulation is bottom-up: fill a table in an order that guarantees every needed entry already exists. They compute the same answers; they differ in style, speed, and failure modes.

This lesson puts both side by side on one non-trivial problem, then gives you a repeatable recipe for designing the state, the single most important decision in any DP. Once you can define the state and the transition, the code almost writes itself.

The problem: cheapest path down a triangle

You are given a triangle of numbers. Start at the top and move to an adjacent number on the row below (directly below, or below and to the right). Add up the numbers you pass. What is the smallest possible sum?

TEXT
        2
       3 4
      6 5 7
     4 1 8 3

Best path: 2 -> 3 -> 5 -> 1 = 11

Brute force: try every path. With n rows there are 2^(n-1) paths, so 30 rows already means over 500 million paths. The structure shows the way out, though. The cheapest path from a cell to the bottom is the cell's own value plus the cheaper of the cheapest paths from the two cells beneath it. That is optimal substructure. And two different cells on one row share the same cells beneath them, so subproblems overlap.

State: best(r, c) = smallest sum of a path that starts at row r, position c and goes down to the bottom row.

Transition: best(r, c) = tri[r][c] + min(best(r+1, c), best(r+1, c+1)).

Base case: on the last row, best(r, c) = tri[r][c].

Answer: best(0, 0).

Top-down: memoization

Write the recursion exactly as the formula reads. Add a cache so each (r, c) is computed once. First the plain version with a call counter, so you can see the waste:

Python Plain recursion on the triangle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 18-row triangle has only 171 cells, yet plain recursion makes 262,143 calls. Now add the memo. There are two idiomatic ways: a hand-written dictionary, or functools.cache.

Python Memoization: dictionary and functools.cache

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The work drops from 262,143 calls to 307. The dictionary stores 153 states (every cell above the last row, each computed exactly once). @cache also caches the 18 base cells, so it reports 171 misses, one per cell; every reuse is a hit.

Pros of memoization

  • Easy to write: translate the recurrence directly.
  • Computes only the states that are actually reachable from the question you asked.
  • Natural for awkward state spaces (strings, tuples, frozensets).

Cons

  • Recursion depth equals the longest chain of dependent states. Python's default limit is about 1000 frames.
  • Function-call overhead and dictionary lookups make it slower per state than a loop.
  • Harder to shrink memory, because you do not control the order.

Bottom-up: tabulation

Tabulation flips the direction. We know the bottom row; the row above depends only on it. So fill the table from the bottom row upwards, with plain loops.

TEXT
table starts as a copy of the last row:   4  1  8  3
row 2:  6+min(4,1)=7   5+min(1,8)=6   7+min(8,3)=10      7  6 10
row 1:  3+min(7,6)=9   4+min(6,10)=10                    9 10
row 0:  2+min(9,10)=11                                  11
Python Tabulation: fill from the bottom row up

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop order is the heart of tabulation. The rule is: iterate so that every state is computed after the states it depends on. Here the dependencies point to the next row, so we go from the last row upward.

Pros of tabulation

  • No recursion limit and less overhead.
  • Easy to see the exact order of work, so it is easy to analyse and optimise.
  • Often allows a memory saving (next section).

Cons

  • You must work out a valid iteration order yourself.
  • It computes every state in the table, even ones the answer never needs.

Space optimisation

In the table version, row r only needs row r + 1. All the older rows are garbage. Keep just one row and overwrite it in place: O(n) extra space instead of O(n^2).

Python One-row version of the triangle DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because row[c] is updated left to right and row[c + 1] has not been overwritten yet at that point, the in-place update is safe. When you compress a table, always double-check the iteration direction so you never read a value you have already overwritten (we will meet the 0/1 knapsack, where the direction is a classic trap).

Reconstructing the path, not only its cost

The DP gives the minimum sum. Often you also need the choices that produced it. Two standard options: store a parent pointer per state while filling, or walk the finished table and ask at each step which child gave the optimum.

Python Recovering the cheapest path itself

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Recursion limits and when to switch

Memoization depth is the length of the longest dependency chain. For a triangle of 18 rows that is 18 calls deep, harmless. For a chain of 50,000 dependent states, the recursion blows through Python's limit; the example below catches the error so you can see it.

Python Hitting the recursion limit with memoization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You can raise the limit with sys.setrecursionlimit, but deep recursion can still crash the interpreter, so tabulation (or an explicit stack) is the safer route for long chains. See recursion for the details.

The state-definition recipe

Every DP problem becomes manageable if you answer these questions in order:

  1. What is the question? Phrase the answer to the whole problem in one sentence.
  2. What information pins down a subproblem? Those are your state variables: an index, a pair of indexes, a remaining capacity, a bitmask. Include just enough to make the subproblem independent of how you reached it, and no more (every extra variable multiplies the number of states).
  3. What does a state's value mean? Write it as a sentence: "best(r, c) is the cheapest path sum from (r, c) to the bottom."
  4. What are the choices at this state? Each choice leads to smaller states.
  5. Write the transition (combine the choices with min, max, +, or or).
  6. Base cases. The states whose answer is known immediately.
  7. Order and answer. Which state holds the final answer, and in what order must states be computed?
  8. Complexity: number of states times work per state.
Memoization Tabulation
Direction top-down bottom-up
Code recursion + cache loops + table
Computes only needed states all states
Recursion limit can hit it never
Space optimisation hard usually easy
Best when state space is sparse or irregular table is dense and the order is obvious

A practical workflow: prototype with @cache to confirm the recurrence is right, then convert to tabulation if the depth, speed or memory demands it.

Common mistakes

  • Missing a state variable. If two different situations share the same (r, c) but need different answers, the state is incomplete and the cached values will be wrong.
  • Wrong fill order. Reading a table cell before it is computed silently uses the initial value (often 0), giving wrong answers rather than errors.
  • Overwriting values you still need when compressing space.
  • Mutable arguments with @cache. Lists and sets are unhashable; use tuples or indexes instead.
  • Forgetting to clear a global memo between test cases that use different input data.
  • Off-by-one on table size. If the state ranges over 0..n, the table needs n + 1 entries.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which description matches memoization?

    Memoization is top-down: the recursive function itself stays, with a cache that stops repeated work.
  2. 2. What is a main advantage of tabulation over memoization in Python?

    Loops do not grow the call stack, so long dependency chains are safe, and there is less per-state overhead.
  3. 3. The triangle DP has 18 rows. Why does the plain recursion need 262,143 calls?

    Plain recursion explores every path from the top (2^18 - 1 calls in total), though only 171 distinct cells exist.
  4. 4. When compressing a DP table to a single row updated in place, what must you check?

    The loop direction decides whether a cell still holds its old value when the next cell needs it.
  5. 5. Which is NOT a step in the state-definition recipe?

    States, meanings, transitions, base cases and ordering are all deliberate; nothing in DP is randomised.

Summary

  • Memoization (top-down) keeps the recursive code and adds a cache; tabulation (bottom-up) fills a table in dependency order with loops.
  • Both give the same answers and the same asymptotic time: number of states times work per state.
  • Memoization computes only reachable states but can hit the recursion limit; tabulation is safer and easier to compress to fewer rows.
  • Define the state precisely (what it means, what variables it needs), then the transition, base cases and order.
  • Reconstruct choices by walking the finished table or by storing parent pointers.
  • Prototype with functools.cache, then convert to loops when depth or memory demands it.

Next: One-Dimensional DP