Dynamic Programming (1D)

Prev Next

Back in the recursion lesson, naive recursive Fibonacci — the version we later sped up with @lru_cache — was the running example of a function that re-solves the same subproblem exponentially many times. Dynamic programming (DP) is exactly the fix for that: recursion plus a systematic way of remembering answers to subproblems you've already solved, so each distinct subproblem is computed once instead of over and over. This lesson covers the two ways to implement that idea — top-down and bottom-up — using Fibonacci as a warm-up and then the "climbing stairs" problem to show the pattern generalizes.

Why Naive Recursion Is Slow: A Quick Recap

fib(5) calls fib(4) and fib(3). But fib(4) itself calls fib(3) again — the exact same subproblem, recomputed from scratch. This branching repeats at every level, giving naive recursive Fibonacci O(2ⁿ) time. DP's insight: there are only n+1 distinct subproblems (fib(0) through fib(n)) — if we remember each one's answer the first time we compute it, every later call becomes an O(1) lookup instead of a re-computation.

Approach 1: Top-Down (Recursion + Memoization)

Keep the same recursive structure, but check a memo before recursing, and store the result after computing it. This is the smallest possible change from "naive recursion that works but is slow" to "recursion that's fast" — which is exactly why it's often the easiest way to discover a DP solution: write the brute-force recursion first, then add memoization. Python gives you two ways to do this: the manual way with a dict, and the idiomatic way with the @lru_cache decorator from functools, which memoizes any pure function automatically.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_top_down(n):
    if n <= 1:
        return n  # base case: fib(0) = 0, fib(1) = 1
    return fib_top_down(n - 1) + fib_top_down(n - 2)

Time complexity: O(n) — @lru_cache caches every distinct call's return value keyed by its arguments, so each of the n+1 distinct subproblems (fib(0)..fib(n)) is computed exactly once; a repeated call like fib_top_down(3) is an instant cache hit instead of a re-computation. Space complexity: O(n) — the cache holds n+1 entries, plus O(n) call-stack depth for the recursion itself.

The manual version below does exactly the same thing by hand, with a plain dict standing in for the cache @lru_cache manages automatically:

# Same idea, written by hand with a dict memo instead of @lru_cache.
def fib_top_down_manual(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]  # already solved this subproblem

    memo[n] = fib_top_down_manual(n - 1, memo) + fib_top_down_manual(n - 2, memo)
    return memo[n]

Time complexity: O(n) — each of the n+1 distinct subproblems (fib(0)..fib(n)) is computed exactly once; every repeat call is an O(1) cache/memo hit. Space complexity: O(n) — the cache/memo holds n+1 entries, plus O(n) call-stack depth for the recursion itself.

Watch the default argument in the manual version: memo=None followed by if memo is None: memo = {} is the safe pattern. Writing def fib_top_down_manual(n, memo={}) directly would be a classic Python bug — the empty dict default is created once when the function is defined and reused across every call, silently accumulating stale entries across unrelated calls.

Approach 2: Bottom-Up (Iterative Table Filling)

Instead of recursing downward from n and hoping the base case is reached, start at the base case and iterate upward, filling a dp list in order so that by the time you need dp[i], both dp[i-1] and dp[i-2] are already filled in. No recursion, no call stack, no decorator.

def fib_bottom_up(n):
    if n <= 1:
        return n

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

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

    return dp[n]

Time complexity: O(n) — a single loop from 2 to n, one O(1) addition per iteration. Space complexity: O(n) for the dp list — though it can be reduced to O(1) here by keeping only the last two values instead of the whole list, since fib(i) only ever depends on its two immediate predecessors.

Top-down vs. bottom-up, in practice: top-down is usually easier to derive (start from the brute-force recursion, decorate it or add a memo) and naturally skips subproblems you never actually need. Bottom-up avoids recursion overhead and Python's recursion limit entirely, and makes space optimization (dropping the full list for a few rolling variables) more obvious. Interviewers are usually happy with either; knowing both means you're never stuck if one doesn't click for a given problem.

Generalizing: Climbing Stairs

Problem: You're climbing a staircase with n steps. Each move you can climb either 1 or 2 steps. How many distinct ways are there to reach the top?

Finding the recurrence: think about the last move to reach step n. It was either a 1-step move from step n−1, or a 2-step move from step n−2. Every distinct way to reach step n falls into exactly one of those two cases, and they don't overlap, so the total count is the sum:

ways(n) = ways(n − 1) + ways(n − 2), with ways(0) = 1, ways(1) = 1

This is the exact same recurrence shape as Fibonacci — which is the real point of this example: once you can spot "the answer for n is built from the answers for n−1 and n−2 (or some other small set of smaller subproblems)," you can reuse the identical top-down/bottom-up machinery for a problem that on the surface looks nothing like Fibonacci.

Top-Down

def climb_stairs_top_down(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return 1  # 1 way to stand still or take one final 1-step
    if n in memo:
        return memo[n]

    memo[n] = climb_stairs_top_down(n - 1, memo) + climb_stairs_top_down(n - 2, memo)
    return memo[n]

Time complexity: O(n) — n+1 distinct subproblems, each solved once. Space complexity: O(n) for the memo dict plus O(n) recursion stack depth.

Bottom-Up

def climb_stairs_bottom_up(n):
    if n <= 1:
        return 1

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

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

    return dp[n]

Time complexity: O(n) — one pass filling n−1 table entries with an O(1) addition each. Space complexity: O(n) for the dp list, reducible to O(1) by tracking only the previous two values.

Next: Fibonacci and climbing stairs both have state that depends on a single changing variable (the index i). Many classic DP problems — like comparing two strings or filling a knapsack — have state that depends on two changing variables, which needs a 2D table instead. That's Dynamic Programming (2D).

Prev Next