Dynamic programming (DP) is a technique for solving problems by breaking them into subproblems — but unlike divide and conquer, DP is specifically for problems where those subproblems overlap, meaning the exact same smaller calculation gets repeated many times if you solve it the naive way. DP's entire value proposition is simple: solve each distinct subproblem once, remember the answer, and reuse it instead of recomputing it.

A problem is a good candidate for DP when it has two properties: overlapping subproblems (the same subproblem shows up again and again) and optimal substructure (the optimal solution to the whole problem can be built from optimal solutions to its subproblems). Fibonacci is the classic first example, even though it's not the most realistic use case — it makes the overlapping-subproblems issue extremely visible.

The Problem: Naive Recursion Repeats Work

A plain recursive Fibonacci function recalculates the same values over and over. Computing fib(5) calls fib(3) twice, fib(2) three times, and so on — the number of redundant calls explodes exponentially, O(2^n), as n grows.

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)  # recomputes shared subproblems

Top-Down: Recursion + Memoization

The top-down approach keeps the same recursive shape, but adds a cache so each unique subproblem is only ever computed once. The first time fib(n) is requested it does the work and stores the result; every call after that is an instant lookup.

def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n in cache:
        return cache[n]  # already solved — reuse it

    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

print(fib_memo(10))

Output:

55

This single change takes the complexity from O(2^n) down to O(n), because each of the n unique subproblems is now solved exactly once.

Bottom-Up: Iterative Table-Building

The bottom-up approach flips the direction entirely — instead of starting at n and recursing down to the base case, it starts at the base case and iteratively builds up to n, filling in a table (or, often, just a couple of variables) as it goes. No recursion, no call stack at all.

def fib_tabulation(n):
    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]

    return table[n]

print(fib_tabulation(10))

Output:

55

Both versions run in O(n) time — the real-world difference between them, and which one to reach for, is covered in our dedicated Memoization vs Tabulation guide. For a less toy example where DP genuinely shines — comparing two sequences rather than a single number — see our Longest Common Subsequence program, a classic 2D DP problem used constantly in diff tools and bioinformatics.

Recognizing a DP Problem

Ask yourself: "If I solved this problem for a smaller input, would that answer help me solve it for a slightly larger input — and would I end up solving the exact same smaller input more than once if I just recursed naively?" If yes to both, you're almost certainly looking at a dynamic programming problem.