What Is Dynamic Programming? A Beginner's Guide to DP

You open a DP problem. You stare at it. It stares back. You write a recursive solution that works on the small examples. You submit it. TLE. You stare at "Time Limit Exceeded" for a while, and then quietly close the tab.

Dynamic programming isn't a mysterious technique that only the enlightened understand. It's a specific response to a specific problem structure: your recursion is computing the same subproblems over and over, throwing away results it already earned. Cache those results, and an O(2^n) disaster becomes O(n). That's the entire idea. The mystique is unearned.

Your Recursive Solution Is Doing the Same Work Twice (And Twice Again)

Start with Fibonacci. Yes, again. Stay with it.

The definition is fib(n) = fib(n-1) + fib(n-2). Write that as code:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Clean. Readable. Correct. Also catastrophically slow.

To compute fib(5), you call fib(4) and fib(3). To compute fib(4), you call fib(3) again. That fib(3) happens twice. By the time you reach fib(40), you're making over a billion function calls. For a sequence that Leonardo Fibonacci described in 1202. The recursion tree is an explosion of repeated work, like hiring someone to count to ten and then immediately hiring a second person to count to ten again.

This is the problem dynamic programming solves. DP says: compute each subproblem once, save the result, never compute it again.

Two Conditions That Tell You DP Applies

Not every slow recursive solution needs DP. The technique applies specifically when two things are true.

Overlapping subproblems: The recursive call tree computes the same subproblems multiple times. In Fibonacci, fib(3) shows up in multiple branches. That repetition is the signal. If your recursion tree looks like a bush rather than a balanced tree, overlapping subproblems are probably why.

Optimal substructure: The solution to a larger problem is built from the solutions to smaller ones. fib(5) depends on fib(4) and fib(3). There's no way to shortcut past the smaller answers.

Both conditions together mean repeated work that can be cached. If you only have optimal substructure but no overlap (like merge sort), plain divide-and-conquer is enough. DP is specifically the response to overlap. See recursion time complexity for a deeper look at why repeated subproblems cause exponential blowup.

Top-Down DP: Put a Cache on the Recursion You Already Have

The simplest DP solution is memoization. Before computing anything, check whether you've already computed it. If yes, return the cached result. If no, compute it, store it, return it.

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

The recursive structure is unchanged. You added four lines. The call tree collapses from O(2^n) to O(n), because every unique subproblem is now solved exactly once.

Each time the recursion tries to recompute fib(3), it hits the cache and returns immediately. The exponential tree becomes a linear sequence. A billion calls becomes forty.

Python's standard library gives you this for free with functools.lru_cache:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

This is called top-down DP because you start from the target (fib(n)) and recurse downward toward the base cases. It's the lazy approach, and I mean that as a compliment.

Bottom-Up DP: Build the Table Forward and Skip the Call Stack Entirely

The other approach inverts the direction. Instead of starting at the answer and recursing toward base cases, start at the base cases and build forward to the answer.

def fib(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]
    return dp[n]

No recursion. No call stack. No risk of Python's recursion limit showing up at fib(1001) to ruin your day. Just an array filled left to right. This is called bottom-up DP or tabulation.

Same O(n) time as memoization. The practical win is avoiding function call overhead and the recursion depth limit (which kicks in around 1,000 frames in Python, a number that sounds large until your input is 1,001).

There's another gain here: once you see the table, you can usually reduce its space. To compute dp[i], you only ever look at dp[i-1] and dp[i-2]. You don't need the full array. Just two variables:

def fib(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

O(n) time. O(1) space. This pattern of collapsing a DP table to a rolling window shows up constantly in practice. The full comparison of the two approaches is in memoization vs tabulation.

A Realistic Example: Coin Change

Fibonacci builds intuition. Coin change shows you what DP looks like on a problem you'd actually see in an interview.

You have coins of denominations [1, 5, 10, 25]. What's the minimum number of coins to make amount 11?

Naive approach: try every combination. That's exponential. Great for small inputs, embarrassing for everything else.

The DP framing: to find the minimum coins for amount 11, you need the minimum for amounts 11 - 1 = 10, 11 - 5 = 6, and 11 - 10 = 1 (the amount left after using each available coin). Each of those depends on even smaller amounts. The subproblems overlap heavily.

The state: dp[a] = minimum coins to make amount a.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # zero coins to make amount zero

    for a in range(1, amount + 1):
        for coin in coins:
            if a - coin >= 0:
                dp[a] = min(dp[a], 1 + dp[a - coin])

    return dp[amount] if dp[amount] != float('inf') else -1

Fill the table from 0 to amount. Each cell uses already-computed values from earlier in the table. The DP state is the single number a, and every possible value of that state gets computed exactly once.

This is LeetCode 322. It shows up at Google, Amazon, and Meta. The underlying pattern (define a 1D state, fill forward using previous cells) transfers to dozens of other problems: climbing stairs, perfect squares, word break. Once you can write coin change from scratch, a whole family of problems opens up.

What Does This Actually Cost?

With memoized Fibonacci:

Time: O(n). Each of n subproblems is solved once.
Space: O(n) for the memo table, plus O(n) for the call stack depth.

With tabulated Fibonacci (space-optimized):

Time: O(n)
Space: O(1)

With coin change:

Time: O(amount * number of coins). Two nested loops; each cell does O(number of coins) work.
Space: O(amount) for the dp array.

The general formula: number of distinct states multiplied by the work per state (not counting the recursive calls themselves). For coin change, states = amount + 1 distinct values, work per state = O(number of coins). Product: O(amount * coins).

This formula applies to almost every DP problem you'll encounter. Identify the state space, count the states, count the work per state, multiply. It sounds mechanical because it mostly is, once you've identified the right state.

DP in Coding Interviews: The Part Nobody Warns You About

DP problems are the category most candidates spend the most time on and still find unpredictable. The reason is that you cannot memorize the solution. Every problem has its own state definition and recurrence relation, and interviewers do not walk in wearing a sign that says "DP problem today."

The skeleton is consistent. You need to:

Define the state (what parameters uniquely identify one subproblem?)
Write the recurrence (how does this state relate to smaller states?)
Identify the base cases
Choose memoization or tabulation
Optimize space if the constraints demand it

Step one is where people get stuck. You see a problem about paths, or coins, or sequences, and you have to recognize that the recursive structure has overlapping subproblems. Then you name the state, write the recurrence, and the rest follows mechanically. The catch is that "name the state" is non-trivial under pressure with someone watching you.

The gap between understanding DP and performing DP under pressure is significant, and it's not closed by reading solutions. Deriving the state definition out loud, in real time, while an interviewer watches, is a skill that needs its own practice. The dynamic programming framework post walks through a repeatable method for doing exactly that.

If you want practice with live feedback on your reasoning process rather than just whether your code passes, SpaceComplexity runs voice-based mock interviews with rubric scoring on your problem-solving approach. DP is one of the categories it covers, and the feedback tracks how you reasoned through the state definition, not just whether you arrived at the right recurrence.

For more on identifying when DP is the right tool and how to spot the signals early, see how to recognize dynamic programming problems.