Memoization vs. Tabulation: Two Ways to Evaluate a DP State

By Hourly DSA · October 5, 2026 · 4 min read

Memoization computes states when recursion asks for them; tabulation computes states in a chosen dependency order. Both can evaluate the same dynamic-programming recurrence. The difference is how you schedule the work and store its results.

Choosing between them is easier after you've defined what a state means.

Start with one precise question

You have unlimited coins of values 1, 3, and 4. What is the fewest number of coins needed to make amount 6?

Let best[a] mean the minimum number of coins that make amount a exactly.

The answer is two coins: 3 + 3. Taking the largest coin first gives 4 + 1 + 1, which needs three. This example needs more than an unproved greedy choice.

For a positive amount a, try each coin that fits. Choosing coin c leaves amount a − c, so that candidate costs 1 + best[a - c].

Take the minimum among valid candidates. Set best[0] = 0, because making zero requires no coins. If no candidate can make an amount, its answer is unreachable, often represented by infinity.

Memoization follows the requests

To answer best[6], a recursive solution requests best[5], best[3], and best[2].

Those requests branch further. Computing best[5] also needs best[2], so the same state can appear through multiple routes.

Memoization checks a cache before expanding a state. Once an answer is computed, later requests reuse it. Each reachable amount is fully evaluated at most once.

The cache must distinguish “not computed” from a valid answer. Zero is the correct answer for amount zero, so treating every zero value as missing can cause unnecessary recomputation or incorrect base-case handling.

Keep the cache tied to the coin set. An answer computed for coins {1, 3, 4} cannot automatically be reused after the available denominations change.

Tabulation follows the dependencies

Every coin is positive, so amount a depends only on smaller amounts. Fill a table from zero upward:

Amount	Minimum coins	One choice
0	0	No coins
1	1	1
2	2	1 + 1
3	1	3
4	1	4
5	2	4 + 1
6	2	3 + 3

At amount 6, the candidates are 1 + best[5], 1 + best[3], and 1 + best[2]. Their values are 3, 2, and 3, so the table stores 2.

The loop order is justified by dependencies. Filling this table downward would read smaller states before their answers were ready.

Compare the actual work and space

For target T and k positive coin denominations, both approaches take O(Tk) time in the worst case and O(T) stored answers, assuming fixed-cost arithmetic.

Memoization also uses a recursion stack. With coin 1 available, a chain can descend one amount at a time, requiring O(T) stack depth. Tabulation avoids that recursive call stack.

Memoization can skip states never requested. Tabulation usually visits every amount up to T. In this example, coin 1 makes all smaller amounts reachable, so demand-driven evaluation doesn't save states.

Don't automatically replace the table with two rolling values. Unlike the stair-counting recurrence, this recurrence may need several different earlier amounts depending on the denominations.

The state matters more than the style

If each coin could be used only once, amount alone would no longer describe the remaining choices. You would need to track which coins are still available, perhaps through an item index and remaining amount.

Changing recursion into a loop would not fix an incomplete state. First preserve the information needed for future decisions, then choose an evaluation order.

Try an unreachable amount

With only coins 3 and 4, what is best[2]?

Unreachable. Neither coin fits, and zero coins make amount zero rather than amount two. Both memoization and tabulation must preserve that distinction.

Use Hourly DSA to practice small changes like this: define the state, identify its dependencies, and check one base case before tracing the algorithm.