Dynamic Programming: Solving Hard Problems by Remembering Answers

Post #10 closed with a genuinely striking number: naive recursive Fibonacci makes 2,692,537 calls to compute fibonacci(30), almost all of them recomputing values already computed elsewhere in the same call tree. Dynamic programming is the direct, precise fix for exactly this waste — remember an answer the first time it’s computed, and simply look it up every subsequent time it’s needed, rather than recomputing it from scratch. Applied to the same Fibonacci function, it turns O(2ⁿ) into O(n) — not a modest improvement, a fundamentally different growth class entirely.

The Core Idea: Remember, Don’t Recompute

Dynamic programming applies specifically when a problem has overlapping subproblems — the same smaller calculation needed repeatedly across different branches of the solution, exactly the pattern Post #10 demonstrated where fibonacci(4) gets computed independently, from scratch, dozens of times while computing fibonacci(10). The fix has two standard forms: memoization (remember results top-down, as you go) and tabulation (build results up from the base case, bottom-up).

Memoization: Top-Down, Remember as You Go

def fibonacci_memo(n: int, cache: dict = None) -> int:
    if cache is None:
        cache = {}
    if n in cache:                 # already computed — this is the entire fix
        return cache[n]
    if n <= 1:
        return n
    result = fibonacci_memo(n - 1, cache) + fibonacci_memo(n - 2, cache)
    cache[n] = result               # remember it, for every future call
    return result

print(fibonacci_memo(30))  # 832040 — instant, versus millions of calls before

This is precisely Post #4’s hash table — cache, a plain Python dictionary — applied directly to Post #10’s exponential recursion problem: before computing fibonacci_memo(n) from scratch, check whether it has already been computed and stored; if so, retrieve it in O(1) (Post #4’s average case) instead of recomputing it.

call_count = 0

def fibonacci_memo_counted(n, cache=None):
    global call_count
    if cache is None:
        cache = {}
    call_count += 1
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    result = fibonacci_memo_counted(n - 1, cache) + fibonacci_memo_counted(n - 2, cache)
    cache[n] = result
    return result

fibonacci_memo_counted(30)
print(call_count)  # 59 — compare directly to the 2,692,537 calls from Post #10's naive version

The difference — 59 calls versus 2,692,537 — is the concrete, measured payoff of this post, and it directly confirms the complexity class change Post #7’s notation predicts: each value from 0 to n is now computed exactly once, giving O(n) instead of O(2ⁿ).

Tabulation: Bottom-Up, Build From the Base Case

def fibonacci_tabulation(n: int) -> int:
    if n <= 1:
        return n

    table = [0] * (n + 1)
    table[1] = 1

    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]  # build each answer from already-known smaller ones

    return table[n]

print(fibonacci_tabulation(30))  # 832040

Rather than starting from fibonacci(n) and recursively working down to the base case (memoization’s top-down approach), tabulation starts at the base case and iteratively builds up to the answer, filling in Post #3’s array (table) one position at a time — no recursion at all, and correspondingly no call stack risk (Post #10’s stack overflow concern) regardless of how large n gets.

Both memoization and tabulation achieve the identical O(n) complexity — the choice between them is largely about style and specific constraints: tabulation avoids recursion’s call stack overhead entirely, while memoization’s structure frequently reads as a more direct translation of the original recursive definition.

The Two Required Properties for Dynamic Programming to Apply

Overlapping subproblems: The same smaller calculation is genuinely needed multiple times across the problem — exactly Fibonacci’s repeated recomputation of the same smaller values, covered directly in Post #10.

Optimal substructure: An optimal solution to the overall problem can be constructed directly from optimal solutions to its subproblems — Fibonacci’s fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) is a direct example, where the correct answer for n depends only on the correct answers for the two smaller subproblems, combined in a fixed, known way.

A problem lacking either property is not a good candidate for dynamic programming — Post #12 covers a genuinely different class of problem, and the important distinction between when each technique applies.

Another Classic Example: Climbing Stairs

“You can climb 1 or 2 steps at a time — how many distinct ways are there to reach the top of an n-step staircase?”

def climbing_stairs(n: int, cache: dict = None) -> int:
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 2:
        return n
    result = climbing_stairs(n - 1, cache) + climbing_stairs(n - 2, cache)
    cache[n] = result
    return result

print(climbing_stairs(10))  # 89

Notice this is structurally identical to memoized Fibonacci — the same overlapping-subproblems, optimal-substructure pattern, just applied to a different real-world question. This is precisely why dynamic programming is taught as a general technique, not a single algorithm: once you recognize the pattern (repeated subproblems, answers built from smaller answers), it applies directly across a genuinely wide range of different-sounding problems.

Real-World Use Cases

Route and resource optimization: Many shortest-path and resource-allocation problems exhibit exactly the overlapping-subproblems structure covered in this post, making dynamic programming a standard technique in logistics and operations research.

Text and sequence comparison: Algorithms comparing two sequences (spell-checkers, DNA sequence alignment, “diff” tools comparing file versions) frequently rely on dynamic programming, since the comparison of longer sequences overlaps heavily with comparisons of their shorter sub-sequences.

Financial and resource-constrained optimization: Classic problems like determining the optimal combination of investments or resources under a budget constraint (the “knapsack problem,” a well-known DP application beyond this post’s scope) rely directly on this technique.

Any recursive solution discovered to be impractically slow: The diagnostic process covered in this post — noticing repeated, identical recursive calls, exactly as Post #10’s call-counting demonstrated — is the standard way real problems get identified as genuine dynamic programming candidates in practice.

Common Mistakes and Gotchas

⚠️ Mistake 1: Applying dynamic programming to a problem without overlapping subproblems If a recursive solution never actually recomputes the same subproblem twice, memoization adds bookkeeping overhead for no benefit — always confirm genuine overlap exists (as this post’s call-counting demonstrated for Fibonacci) before assuming DP will help.

⚠️ Mistake 2: Forgetting to actually use the cache before recursing

def broken_memo(n, cache):
    if n <= 1:
        return n
    result = broken_memo(n - 1, cache) + broken_memo(n - 2, cache)  # BUG — never checks cache first!
    cache[n] = result
    return result

The cache-check must happen before the recursive calls, not merely after computing the result — a genuinely easy detail to miss that silently eliminates the entire performance benefit while still appearing to work correctly.

⚠️ Mistake 3: Choosing tabulation for a problem where most of the table would never actually be needed If a problem only genuinely requires a small, specific subset of subproblems (rather than every value up to n), memoization’s on-demand, top-down computation can be more efficient than tabulation’s exhaustive, bottom-up table-filling — the “always tabulate” instinct is not universally correct.

⚠️ Mistake 4: Assuming any recursive function benefits from memoization Covered directly above — memoization specifically fixes redundant recomputation of identical subproblems; a recursive function where every call has genuinely unique arguments gains nothing from caching, since no cache hit will ever occur.

Quick Reference

# Memoization — top-down, cache as you recurse
def solve_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if base_case_condition:
        return base_case_answer
    result = combine(solve_memo(smaller_n, cache), ...)
    cache[n] = result
    return result

# Tabulation — bottom-up, build an array from the base case
def solve_tabulation(n):
    table = [None] * (n + 1)
    table[0] = base_case_answer
    for i in range(1, n + 1):
        table[i] = combine(table[i - 1], ...)
    return table[n]

When DP applies: overlapping subproblems (the same smaller calculation needed repeatedly) + optimal substructure (the answer builds directly from smaller answers).

Exercises

Exercise 1 — Direct application Add call-counting to climbing_stairs (exactly as this post did for Fibonacci) both with and without memoization, and compare the actual call counts for n = 20.

Exercise 2 — Slight variation Rewrite climbing_stairs using tabulation instead of memoization, and confirm it produces identical results to the memoized version.

Exercise 3 — Real-world combination Write a memoized function min_coins(amount, coin_values) that returns the minimum number of coins needed to make a given amount using unlimited coins of each given denomination — a genuinely classic DP problem, directly setting up Post #12’s exploration of exactly when a simpler, faster approach also happens to work for this same problem.

Exercise 4 — Open-ended challenge Using this post’s call-counting technique, verify that memoized Fibonacci’s call count grows linearly (roughly proportional to n) rather than exponentially, by measuring the call count at n = 10, 20, and 30, and confirming the growth pattern matches Post #7’s O(n) prediction rather than the O(2ⁿ) pattern from Post #10’s naive version.

FAQ

Q: Is dynamic programming always the right choice when a recursive solution is slow? A: Specifically when the slowness comes from overlapping subproblems, covered throughout this post — for other causes of slowness (genuinely necessary, non-redundant work at every step), memoization provides no benefit at all, since there is nothing repeated to avoid recomputing.

Q: Does memoization work correctly if a function has side effects or depends on external, changing state? A: No — memoization assumes a function is “pure” in the sense covered in this blog’s JavaScript series (same input always produces the same output) — caching the result of a function whose output can genuinely vary for the same input produces incorrect, stale results.

Q: Which is generally preferred in real code, memoization or tabulation? A: Both are entirely valid and widely used — memoization is often more natural when adapting an existing recursive solution (exactly as this post did with Fibonacci), while tabulation is often preferred when avoiding recursion’s call stack overhead matters, or when the iterative, bottom-up structure more directly matches how you’re already thinking about the problem.

Q: How much memory does memoization actually use? A: The cache itself uses O(n) additional space (Post #7’s space complexity coverage) in Fibonacci’s case, storing one entry per distinct subproblem — a genuine, real tradeoff (memory for speed) worth being aware of, though for most practical problems this space cost is dramatically smaller than the time saved.

Summary and Next Steps

You now understand dynamic programming as the precise, direct fix for exactly the problem Post #10 demonstrated concretely — overlapping subproblems recomputed wastefully — using either memoization’s top-down caching (built directly on Post #4’s hash tables) or tabulation’s bottom-up array-building (built directly on Post #3’s arrays). The 2,692,537-versus-59 call count difference for fibonacci(30) is not a marginal optimization; it is the difference between O(2ⁿ) and O(n), exactly the complexity class distinction Post #7 established as the difference between “impractical at scale” and “genuinely efficient.”

Your next step: Complete Exercise 3 — the coin-change minimum-coins problem — since it is a genuinely classic, practically important DP problem in its own right, and it sets up directly for Post #12’s exploration of when a much simpler approach also happens to produce the correct answer for this same problem, and precisely when it does not.

Last updated: August 2026.