Dynamic Programming for Beginners: Memoization vs Tabulation

Dynamic Programming (DP) is a powerful technique for solving optimization problems by breaking them into smaller subproblems. It has a reputation for being hard, but most of that difficulty is packaging. The underlying idea is almost embarrassingly simple: if you keep solving the same small problem over and over, write the answer down the first time and read it back later. Everything else is bookkeeping about where you write it down and in what order.

The Core Idea

DP solves problems by doing three things.

1. Breaking them into overlapping subproblems
2. Storing results to avoid recomputation
3. Building up solutions from smaller solutions

Two properties tell you a problem is a candidate. The first is overlapping subproblems: the same smaller question comes up again and again as you recurse. The second is optimal substructure: the best answer to the whole is assembled from the best answers to its parts. When both hold, caching turns an exponential search into a linear or polynomial walk. When they do not, DP is the wrong tool, and a greedy rule or plain divide and conquer usually fits better.

A quick gut check: sketch the recursion tree for a small input. If the same node label shows up on more than one branch, you have overlap, and DP will help. If every node is unique, there is nothing to cache and you are just paying for the table.

The brute force we are escaping

It helps to see the waste before you remove it. Here is Fibonacci written the obvious way, with no memory.

def fib_naive(n):
    if n <= 2:
        return 1
    return fib_naive(n - 1) + fib_naive(n - 2)

This is correct and completely impractical. Computing fib_naive(n) spawns two calls, each of which spawns two more, and the recursion tree keeps branching until it reaches a base case. The two branches overlap badly: fib(n - 1) and fib(n - 2) both recompute fib(n - 3) from scratch, and that duplication repeats the whole way down. The number of calls grows on the order of the Fibonacci numbers themselves. To get fib(20) the naive version makes more than thirteen thousand calls, and fib(50) would run longer than anyone wants to sit and watch.

Memoization and tabulation both attack that duplication. They differ only in direction.

Memoization (Top-Down)

Memoization uses recursion with caching.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

The shape of the recursion is identical to the naive version. The only change is the cache: before doing work we check whether the answer is already known, and after computing it we store it. Every distinct n is now solved exactly once, so those thirteen thousand calls collapse to a few dozen.

What works well

• Intuitive (follows problem structure)
• Only computes needed subproblems

Tradeoffs

• Recursion overhead
• Stack overflow risk for deep recursion

Tabulation (Bottom-Up)

Tabulation builds solutions iteratively.

def fib_tab(n):
    if n <= 2:
        return 1
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Here we flip the direction. Instead of starting at n and recursing down, we start at the base cases and fill forward. By the time the loop reaches index i, everything it depends on is already sitting in the table, so there is no recursion and no cache lookup, just an array and a loop.

What works well

• No recursion overhead
• Better space optimization possible

Tradeoffs

• May compute unnecessary subproblems
• Less intuitive for some problems

Tabulation also opens the door to a space trick. Notice that fib_tab only ever reads the last two entries of the table. We can throw the rest away and keep two running variables, which drops the memory from linear to constant.

def fib_rolling(n):
    if n <= 2:
        return 1
    prev, curr = 1, 1
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr

That rolling rewrite is a habit worth building. A surprising number of one-dimensional DP problems only look back a fixed distance, and each one can shed its full table the same way.

A worked example, step by step

Fibonacci is the friendly introduction, but it hides the part that makes DP interesting: a real choice at every step. Coin change is the classic next problem. Given a set of coin denominations and a target amount, find the fewest coins that sum to it.

Start by naming the state. Here it is "the minimum number of coins needed to make amount a." Then write the recurrence in words: to make a, try every coin c that fits, and take one of that coin plus the best way to make a - c. The base case is that making zero costs nothing.

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

Walk it with coins = [1, 2, 5] and amount = 6, filling the table from the bottom up.

• dp[0] = 0. Making zero takes no coins.
• dp[1] = 1. Only the 1 coin fits, stacked on dp[0].
• dp[2] = 1. The single 2 coin beats two 1 coins.
• dp[3] = 2. Best is a 2 plus a 1.
• dp[4] = 2. Two 2 coins.
• dp[5] = 1. The 5 coin lands directly on dp[0].
• dp[6] = 2. A 5 coin plus dp[1] wins, so a 5 and a 1.

The answer is dp[6] = 2. Watch how each cell reuses cells we already solved. That is the overlapping structure that makes the caching pay off, and it is the same reason the naive Fibonacci was so wasteful.

Often you want the actual coins, not just how many. The table already knows: at each amount, remember which coin gave the minimum, then walk backward from the target following those choices. This split, one pass to compute the best value and a second pass to reconstruct the decisions that produced it, shows up across DP and is worth practicing early.

Every DP solution, once you have written a few, follows the same short recipe.

Reading the complexity

Big-O is easier to trust when you can say it in plain words. Naive Fibonacci runs in exponential time because the recursion tree roughly doubles at each level and the same values get rebuilt on every branch. Memoization and tabulation both flatten it to linear time: there are n distinct subproblems, each costs constant work once its inputs exist, so the total is proportional to n.

Space is where the two styles part ways. Memoization holds a cache of size n plus a recursion stack that can grow n frames deep, which is exactly what triggers a stack overflow on large inputs. Tabulation holds a table of size n with no stack at all, and the rolling version trims even that down to constant space because it only remembers the last two values.

Coin change reads the same way. The outer loop runs over every amount up to the target, and the inner loop tries every coin, so the running time is proportional to the amount times the number of coins. The table stores one entry per amount, so the space is proportional to the target. Naming the two loops out loud like this is often faster than staring at the code trying to pattern-match a formula.

Choosing a style

• Memoization fits when you do not need every subproblem value up front, when the recursion mirrors the problem cleanly, or when only a sparse slice of the state space is ever reached.
• Tabulation fits when you want a filled table, tighter space control, or an iterative story that sidesteps deep recursion and its stack limits.

In practice many people prototype with memoization, because it is a tiny edit to a recursive solution they already trust, then convert to tabulation once the recurrence is proven correct and they want the speed or the constant-space rewrite. Both compute the same answers. They just disagree about who goes first.

Common mistakes

• Missing or wrong base cases. The base cases anchor the entire recurrence. Get them wrong and every value above them inherits the error, sometimes as an infinite loop that never bottoms out.
• Filling the table in the wrong order. In tabulation a cell must be computed after everything it depends on. If dp[i] reads dp[i - 2], that earlier entry has to be ready first, or you are reading uninitialized garbage.
• An incomplete state. The cache key has to capture everything that changes the answer. If two genuinely different situations map to the same key but deserve different results, the memo will hand back the wrong one without complaint.
• The shared mutable default. In Python a default argument like memo={} is created once and reused across every top-level call. As a cache it can even look helpful, but it quietly persists between separate calls, which surprises people the moment they write tests. Passing in a fresh dict, or resetting inside a wrapper function, keeps the behavior predictable.
• Ignoring the impossible case. In coin change some amounts cannot be formed at all. The infinity sentinel plus the final guard is what turns that into a clean -1 instead of a meaningless number.

Classic DP problems

1. Fibonacci as the smallest introduction
2. Climbing stairs as a close cousin
3. Coin change for real optimization practice
4. Longest common subsequence when you are ready for 2D tables

Solve them in that order and each one adds exactly one new idea. Climbing stairs is Fibonacci with a story attached. Coin change adds a real choice at every step. Longest common subsequence stretches the table into two dimensions, which is where most interview DP actually lives.

When to reach for DP

Reach for DP when you catch yourself solving the same subproblem twice and the best overall answer is built from best sub-answers. That pairing, overlapping work plus optimal substructure, is the tell. If the subproblems never repeat, caching buys you nothing and plain recursion or divide and conquer is cleaner. If a single greedy choice is provably safe at each step, take the greedy route, because it is simpler and usually faster. DP earns its place in the middle ground, where you have to weigh many choices and the same intermediate results keep resurfacing. Start with the four problems above, write the recurrence in words before you write any code, and the pattern stops feeling like a trick and starts feeling like a checklist.