Skip to content
Essay · Craft

What is the difference between memoization and tabulation

The difference between memoization and tabulation is direction: top-down caching of a recursion versus a bottom-up loop over a table. Here is what that changes in work done, stack depth, memory, and which one to reach for.

By Vishy9 min readPublished · 15 Nov 2026

The difference between memoization and tabulation is the direction of evaluation. Memoization is top-down: you write the recursion, then cache results as calls return. Tabulation is bottom-up: you fill a table in dependency order with loops. Both solve the same subproblems once; they differ in which subproblems get computed, stack use, and how easy space optimisation is.

Most explanations stop there and show Fibonacci twice. That hides every interesting consequence, because in Fibonacci the two approaches touch exactly the same states. In real problems they do not, and the gap shows up in three places: how many states you compute, whether the stack survives, and how much memory you can throw away. I will work through each with numbers, then give the rule I actually use.

What are memoization and tabulation, in code?

Memoization is a recursive function plus a cache keyed by its arguments; tabulation is the same recurrence turned into loops that fill an array from the smallest subproblem upward. The recurrence itself is identical. Only the scheduling changes.

Take the minimum number of coins needed to make an amount, which is the classic shape behind Coin Change. The recurrence says: the best answer for amount a is one coin plus the best answer for a - c, minimised over every coin c that fits. Here it is top-down:

from functools import lru_cache

def min_coins_memo(coins, amount):
    @lru_cache(maxsize=None)
    def best(a):
        if a == 0:
            return 0
        result = float('inf')
        for c in coins:
            if c <= a:
                result = min(result, 1 + best(a - c))
        return result
    ans = best(amount)
    return -1 if ans == float('inf') else ans

And bottom-up:

def min_coins_tab(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return -1 if dp[amount] == INF else dp[amount]

The loop body in the second version is the body of the function in the first. The memoized version asks for what it needs, when it needs it. The tabulated version computes everything up to the target in an order that guarantees each dependency is ready. I think of it as two kitchens. The memoizing cook chops onions only when an order arrives and keeps the leftovers on the board. The tabulating cook does the full prep before service, so nothing is ever waited on, but some of that prep may never be used.

If the recurrence part is the hard part for you, that is a separate skill, covered in the state design template. Memoization versus tabulation only matters once you already have a correct recurrence.

Which one does less work?

Memoization never does more work than tabulation on the same recurrence, and it often does much less, because it only visits states that are reachable from the starting call. Tabulation visits every state in the table whether or not anything needs it.

Here is a case where the difference is not subtle. Coins of 50 and 100, target 10,000. Count the work three ways.

  • Plain recursion, no cache. Subtracting 50 or 100 repeatedly is the same as taking steps of size 1 or 2 across 200 units (10,000 divided by 50). The number of distinct step sequences follows the Fibonacci recurrence, so it is over 1041. No machine finishes that.
  • Memoized. The only amounts ever reached are 10,000 minus a multiple of 50, which gives 201 distinct states. Each state tries two coins, so about 402 transitions, plus a few cache hits that return immediately.
  • Tabulated over amounts 0 to 10,000. The table has 10,001 cells and each tries two coins, so 20,002 checks. Roughly 9,800 of those cells are amounts like 7 or 4,321 that can never be formed and never matter.

That is about a 50x gap, and it comes entirely from the structure of the input. In the worst case for memoization, say coins of 1 and 2, the reachable set is the whole table and the two approaches do the same work, with memoization paying a constant-factor premium for function calls and hashing.

You can close the gap on the tabulation side by dividing everything by the gcd of the coins first. But notice what that is: you are manually discovering which states are reachable. Memoization finds that out for free. This is the strongest argument for top-down when you are not sure how sparse the state space is.

There is an honest counterpoint. When the table is dense, a tight loop over a flat array beats recursion with hashed lookups, often by a factor of three to ten in an interpreted language. So the right sentence is not that memoization does less work. It is that memoization does fewer states, and tabulation does cheaper states.

When does the recursion stack make memoization the wrong choice?

Memoization is the wrong choice when the longest dependency chain is deeper than your runtime allows, because every pending call holds a stack frame. Tabulation uses a loop, so its depth is always constant.

Stay with the same coins, but make the target 1,000,000. The reachable states number only 20,001, so memoization looks wonderful on paper. But the first branch of the recursion subtracts 50 every time until it hits zero, and that is a call chain 20,000 deep. CPython's default recursion limit is about 1,000, so the program dies with a RecursionError long before it finishes. You can raise the limit, but you then risk exhausting the real C stack, and the failure becomes a segfault rather than an exception. Tabulation over a million cells just runs: 1,000,001 cells times two coins is about two million checks, which is trivial.

Languages differ here. Java defaults to a stack that tolerates somewhere around ten to twenty thousand simple frames. Go grows its stacks dynamically and is far more forgiving. C++ depends on your platform and what each frame holds. The general rule is stable: depth of recursion equals longest chain of dependent subproblems, and for many one-dimensional DP problems that chain is as long as the input. If you want the broader treatment of what a call costs, I wrote about it in is recursion slower than iteration.

The workaround, if you love the top-down style, is to warm the cache from small to large before the real call: loop a from 0 to the target calling best(a). Each call then finds its dependencies already cached and the depth stays at one or two. At that point you have written tabulation with extra steps, which tells you something about how close the two techniques really are.

Why does tabulation make space optimisation easier?

Tabulation makes space optimisation easier because the evaluation order is explicit, so you can see exactly when a row or cell is last read and discard it. A memo cache has no such visible schedule, so it tends to keep everything.

Consider longest common subsequence on two strings of 5,000 characters each. The state is a pair of prefix lengths, so there are 5,001 times 5,001, about 25 million states. Memoized with a dictionary keyed by (i, j), every visited pair stays in memory. In CPython that is gigabytes once you count tuple keys, hashed buckets, and boxed integers, and you will likely get killed by the OS before you finish.

Tabulated, row i only reads row i - 1 and the earlier part of itself. Keep two rows of 5,001 integers and you are using about 10,000 cells instead of 25 million, a reduction of 2,500x, with the same time complexity of O(mn). The same trick collapses a 0/1 knapsack from a two-dimensional table to a single array if you iterate the capacity downward. You can see the shape of this in the knapsack variants.

You can do the equivalent with memoization by evicting entries manually, but you have to reason about the schedule yourself, and at that point you have reinvented the loop order. The rule I trust: if a problem asks for the value only (not the reconstruction of the choices), and the table is large, tabulate and roll the table. If you need to reconstruct the path, you typically need the full table or a compact parent pointer array, and the memory saving shrinks.

How do the two approaches compare side by side?

Memoization wins on ease of writing and on sparse state spaces; tabulation wins on stack safety, constant factors, and memory control. The table below is the comparison I keep in my head.

PropertyMemoization (top-down)Tabulation (bottom-up)
States computedOnly reachable ones (201 in the coin example)All in the table (10,001 in the coin example)
Cost per stateHigher: call overhead plus hash lookupLower: array index in a loop
Stack depthUp to the longest dependency chainConstant
Memory shapeWhatever was visited, usually all of itFull table, but can be rolled to one or two rows
Need an evaluation orderNo, recursion supplies itYes, you must get the loop order right
Closest to the recurrenceAlmost a transliterationOne step removed
Typical failureRecursionError or out of memory on a big cacheWasted work on unreachable states

The row about evaluation order is the one beginners underrate. In a two-dimensional problem, getting the loop direction wrong is a real source of bugs, because a cell can silently read a value that has not been written yet and you get an answer that looks plausible. Memoization cannot make that mistake, since a missing value simply triggers the recursive call. If you want to practise the underlying habit of reasoning from smaller cases to larger ones, recursion as induction is the framing that makes both styles feel like one idea.

Which should I use in a coding interview?

Start with memoization to get a correct solution quickly, then convert to tabulation if the interviewer asks about stack depth or memory, or if the table is obviously dense. That order minimises the chance of a wrong answer under time pressure.

My reasoning is practical. Under pressure, the hardest part is the recurrence and the base cases, and top-down lets you write them in the same shape you derived them. You can check correctness by hand on a tiny input, add the cache in one line, and have a working O(states) solution in a few minutes. The conversion afterwards is mechanical: the arguments of the function become table indices, the base cases become initial values, and the order of the loops follows the direction of the dependencies. Saying that conversion out loud also shows the interviewer that you understand the two are one idea in two schedules, which is a better signal than having memorised either.

There are cases where I would go straight to tabulation. One is a one-dimensional problem whose input can be 105 or 106, where depth would kill a recursive version in Python or Java. Another is a problem that obviously needs the last row or two only, such as a grid path count, where the rolled array is the point. A third is when I know every state is needed, like the standard maximum subarray recurrence, where there is nothing sparse to exploit. For the broader question of why this style of problem feels hard, why is dynamic programming so hard covers the part that comes before this choice.

One habit that has served me: before choosing, ask two questions. First, how deep is the longest chain? If it is about as long as the input and the input is large, tabulate. Second, is the reachable set plausibly much smaller than the full grid of states? If so, memoize. If neither applies, pick whichever you can write correctly fastest.

Frequently asked questions

Is memoization the same as dynamic programming?

Memoization is one way to implement dynamic programming, not a separate thing. Dynamic programming is the idea that a problem has overlapping subproblems with optimal substructure; memoization and tabulation are the two standard schedules for solving each subproblem once.

Is tabulation always faster than memoization?

No. Tabulation has lower cost per state, but it computes every state, while memoization computes only reachable ones. With 201 reachable states against 10,001 table cells, as in the coin example, memoization does about fifty times fewer transitions even though each is slower.

Why does my memoized solution crash with a recursion error?

Each unfinished call holds a stack frame, so the depth equals the longest chain of dependent subproblems. If that chain is tens of thousands long, Python's default limit of about 1,000 is exceeded. Convert to a bottom-up loop, or warm the cache from small inputs to large so each call finds its dependencies already stored.

If you want to feel both schedules on the same recurrence, solve Coin Change twice, once top-down and once bottom-up, then count the states each version actually touches.