Memoization vs Tabulation in Dynamic Programming

Memoization and tabulation are the two ways to write dynamic programming. Memoization is top-down: a recursive function caches its answers, so it is easy to derive and only computes the states it reaches. Tabulation is bottom-up: a loop fills a table in order, with no recursion, and it often lets you keep only the last few values.

Memoization and tabulation compared

	Memoization, top-down	Tabulation, bottom-up
How it runs	Recursion with a cache	A loop over a table
Time	States times work per state	States times work per state
Space	O(states) plus the call stack	O(states), often less
States computed	Only those reached	All of them
Order of computation	Worked out for you by the recursion	You must choose it
Can drop to O(1) space	Rarely	Often, when only recent states are read
Risk	Recursion limits on deep inputs	Reading a state before it is filled
Best when	The recurrence is clear but the order is not	Every state is needed, or memory matters

A worked example where both apply

Given coin values and an amount, find the fewest coins that add up to it, or -1 if none do. The state is the same in both versions: the fewest coins for each smaller amount. Greedy fails here: with coins of 1, 3 and 4, an amount of 6 is two coins (3 + 3), not the three that taking the largest first gives (4 + 1 + 1).

from functools import lru_cache

def fewest_coins_memo(coins, amount):
    @lru_cache(maxsize=None)
    def best(left):                       # fewest coins to make exactly left
        if left == 0:
            return 0
        if left < 0:
            return float("inf")
        return 1 + min(best(left - c) for c in coins)
    answer = best(amount)
    return answer if answer != float("inf") else -1

def fewest_coins_table(coins, amount):
    table = [0] + [float("inf")] * amount # table[a]: fewest coins to make a
    for a in range(1, amount + 1):        # smaller amounts are already filled
        for c in coins:
            if c <= a:
                table[a] = min(table[a], table[a - c] + 1)
    return table[amount] if table[amount] != float("inf") else -1

Both are O(amount · coins) time and O(amount) space. They differ in how they fail. The memoized version recurses as deep as the amount when a coin of 1 exists, so a large amount can hit Python's recursion limit. The table has no such limit, and the choice of order is simple here, because every state reads only smaller amounts.

Which to pick in an interview, and how to say why

Start with memoization if you already have the recursive solution, or the fill order is not obvious. It is the shortest way from a working brute force to a correct answer.
Use tabulation when every state is needed anyway, when the input is deep enough to threaten the recursion limit, or when the interviewer asks you to reduce the space.
Offer the conversion. Writing it top-down and then saying how you would turn it into a loop shows you understand both.

What a strong candidate might say

The recursion repeats the same amounts many times, so I'll cache by the amount left, which turns an exponential tree into one call per amount. That's O(amount times coins) time and O(amount) space. The recursion could go as deep as the amount, so if the inputs are large, I'd rewrite it as a table filled from zero upward, which has the same time with no risk of hitting the stack limit.