Dynamic Programming Explained: Memoization, Tabulation, and Classic Problems

Dynamic programming is not a single algorithm but a problem-solving technique. Once you recognise the two conditions that make a problem a DP candidate, you can cut exponential runtimes down to polynomial ones with a cache or a table.

What Makes a Problem Suitable for Dynamic Programming

Dynamic programming applies when a problem has two specific properties. The first is overlapping subproblems: the same smaller problem appears multiple times in the recursive breakdown. This is the key distinction from classic divide-and-conquer algorithms like mergesort, where each subproblem is independent and never recalculated. The second property is optimal substructure: an optimal solution to the overall problem can be constructed from optimal solutions to its subproblems. Shortest paths, minimum-cost sequences, and longest subsequences all have this property.

When both properties hold, naive recursion wastes enormous time recomputing results it has already seen. Dynamic programming stores those results, either by caching as you recurse (memoization) or by filling a table iteratively from the smallest subproblems upward (tabulation).

Worked Example 1: Fibonacci Numbers

The Fibonacci sequence is the clearest illustration of why naive recursion fails for overlapping problems. The naive recursive implementation looks elegant but has exponential time complexity:

# BEFORE: naive recursion
# Time: O(2^n) -- an exponential tree of redundant calls
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# fib_naive(40) makes over a billion recursive calls.

To compute fib(5), this function computes fib(3) twice, fib(2) three times, and fib(1) five times. The call tree has exponential branches because neither branch knows what the other has already computed. The fix is top-down memoization: add a cache dictionary and return a stored result if the answer is already known.

# AFTER: top-down memoization
# Time: O(n) -- each subproblem computed exactly once
# Space: O(n) -- the memo cache
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# fib_memo(1000) returns instantly.

Each value of n is now computed at most once. The recursion tree collapses from exponential to linear depth. Time complexity drops from O(2^n) to O(n) and space is O(n) for the cache. You can shrink space to O(1) with a bottom-up loop that only keeps the last two values, but the memoised version is often easier to reason about when you are first translating a recurrence into code.

Top-Down vs Bottom-Up: Two Ways to Store Subproblem Results

Top-down (memoization) is recursive. You write the natural recursive solution, add a cache, and return early on a hit. It only computes the subproblems actually needed for the answer, which can be an advantage when the problem space is sparse.

Bottom-up (tabulation) is iterative. You identify the smallest subproblems, solve them first, store results in an array or table, and build upward until you reach the answer. It avoids recursion overhead and stack depth limits entirely, which makes it preferable for large inputs. Both approaches produce the same asymptotic complexity. The choice is often a matter of which one maps more cleanly onto the problem structure.

Worked Example 2: Coin Change

Given a set of coin denominations and a target amount, find the minimum number of coins that sum to that amount. This is a classic DP problem because the optimal number of coins for amount A depends on the optimal number for amounts A minus each coin denomination.

The bottom-up tabulation approach fills an array dp where dp[i] is the minimum coins needed to make amount i:

# Bottom-up tabulation for coin change
# Time: O(amount * len(coins))
# Space: O(amount)
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0   # zero coins needed to make amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                # try using this coin and add 1 to the result for (i - coin)
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# Example:
# coins = [1, 5, 10, 25], amount = 36
# coin_change([1, 5, 10, 25], 36) returns 3 (25 + 10 + 1)

At each amount i, the algorithm tries every coin and picks the one that gives the smallest total count. The key insight is that dp[i - coin] is already solved by the time we reach i, because we fill the table from 0 upward. There is no recursion, no risk of stack overflow, and the solution naturally handles all subproblems in order.

Other Classic DP Problems

The same patterns appear in many well-known problems. The Longest Common Subsequence (LCS) problem asks for the longest sequence of characters that appears in the same order in two strings (not necessarily contiguous). It builds a 2D table of size m x n where each cell stores the LCS length for a prefix of each string. LCS underlies the Unix diff utility and sequence alignment in bioinformatics.

The 0/1 knapsack problem, edit distance, and matrix chain multiplication all follow the same pattern of defining a recurrence over subproblems and filling a table to avoid recomputation.

When DP Applies vs Greedy

A greedy algorithm makes the locally optimal choice at each step without reconsidering past decisions. Greedy is faster (often O(n log n) vs O(n^2) for DP), but it only produces the global optimum when the problem has the greedy choice property, meaning the locally optimal choice is always part of some globally optimal solution. Coin change with standard denominations (1, 5, 10, 25) happens to have this property, so a greedy algorithm works. But with arbitrary coin sets it fails, and DP is the correct tool.

As a rule: if you can prove the greedy choice property holds, use greedy. If you cannot, fall back to DP. The discipline of recognising recurrences connects directly to the material in our recursion explained guide and to the complexity analysis in our big-O notation article.