Dynamic Programming

Overview

Dynamic programming (DP) solves complex problems by breaking them into overlapping subproblems and storing each answer so it is computed only once. It applies when a problem has optimal substructure and repeated subproblems, like Fibonacci or shortest paths. DP trades extra memory for a large drop in time, often from exponential to O(n).

Syntax / Usage

Top-down DP adds memoization to recursion; bottom-up DP fills a table iteratively. Both avoid recomputing the same subproblem.

def fib_memo(n, cache=None):             # top-down: O(n) time, O(n) space
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n not in cache:
        cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

def fib_table(n):                        # bottom-up: O(n) time, O(1) space
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

Examples

Memoization turns exponential Fibonacci into linear time:

print(fib_memo(30))   # 832040, computed quickly
print(fib_table(30))  # 832040, using constant space

Bottom-up DP counts the ways to climb stairs taking 1 or 2 steps:

def climb_stairs(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(climb_stairs(5))  # 8

Common Mistakes

• Using DP without overlapping subproblems, where plain recursion is simpler.
• Sharing a mutable default cache across calls, causing stale results.
• Incorrect base cases that shift every computed value.
• Building an O(n) table when two variables would give O(1) space.
• Confusing DP with greedy; DP explores all options, greedy commits to one.

See Also

algorithms-recursion algorithms-greedy algorithms-big-o-notation