Dynamic Programming Basics — Fixing Overlapping Subproblems

Build the mental model

Dynamic programming applies when a problem has two properties: optimal substructure (the best solution to the whole problem is built from best solutions to its subproblems) and overlapping subproblems (those subproblems repeat, rather than being all distinct). Naive recursive Fibonacci is the textbook illustration of what happens when you have both but ignore the overlap: fib(n) calls fib(n-1) and fib(n-2), fib(n-1) itself calls fib(n-2) and fib(n-3), and fib(n-2) gets computed independently by both branches. This redundancy compounds recursively, so the total number of calls grows exponentially, O(2^n) — computing fib(40) naively means over a billion redundant calls for a number a calculator produces instantly. The fix is recognizing that fib(k) is the same value no matter which call path reached it, so it only needs to be computed once. Memoization does this top-down: keep the natural recursive structure, but cache each result in a dict keyed by input, checking the cache before recomputing. Tabulation does it bottom-up: build an array iteratively from fib(0) and fib(1) up to fib(n), no recursion at all. Both eliminate the redundant recomputation, dropping the cost to O(n).

Connect it to a real scenario

The Tutorial Platform's 'shortest learning path covering all prerequisites' problem is a natural fit for dynamic programming: computing the minimum-lesson-count path to a goal that satisfies every prerequisite dependency has overlapping subproblems — the optimal path to lesson X often gets reused as a prefix of the optimal path to several later lessons, just like fib(n-2) gets reused by both fib(n) and fib(n-1). Recomputing the best prerequisite chain from scratch for every goal lesson, ignoring that overlap, would scale exponentially as the topic graph grows. Caching each lesson's already-solved 'minimum lessons to reach here satisfying prerequisites' result — exactly memoization's approach — turns an intractable brute-force search into a fast, linear-in-lesson-count computation the platform can run on every path request.

Dynamic programming applies when a problem has both optimal substructure and overlapping subproblems.
Naive recursive Fibonacci is O(2^n) because it recomputes the same subproblems repeatedly.
Both memoization (top-down caching) and tabulation (bottom-up array building) fix this to O(n) by eliminating redundant recomputation.

Try the working example

python

def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)  # recomputes the same subproblems repeatedly

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

print(fib_naive(20))   # O(2^n): fine for small n, but blows up fast
print(fib_memo(60))    # O(n): each subproblem solved and cached exactly once

You should see

Prints 6765 (fib_naive(20)), then instantly prints 1548008755920 (fib_memo(60)) — a value the naive version couldn't compute in any practical time at n=60.

5-minute try-it

Rewrite fib_memo as bottom-up tabulation (no recursion — iteratively fill an array from fib(0) up to fib(n)) — verify it produces the same results as the memoized version.

One important caution

Using a mutable default argument like fib_memo(n, cache={}) without realizing Python creates that default object once, shared across all calls, not fresh per call — here it's deliberately exploited as a shared cache, but the same pattern causes real bugs in other contexts.

Forgetting that memoization cache keys must be hashable — trying to memoize a function whose input is an unhashable type (like a list) crashes with a TypeError that catches learners off guard.

Wikipedia — Dynamic programming — Data Structures & Algorithms