Dynamic Programming

After this lesson, you will be able to: Recognize dynamic programming problems, apply memoization (top-down) and tabulation (bottom-up), and solve classic DP problems like coin change and longest common subsequence.

Dynamic programming sounds intimidating but is one idea: when a recursive solution recomputes the same subproblems, store the results and reuse them. That single move turns exponential algorithms into polynomial ones. DP is the most feared interview topic, so understanding the thought process is a real edge.

Prerequisites:Recursion

The core idea: stop recomputing

Dynamic programming applies when a problem has two properties. Overlapping subproblems: the same smaller problems are solved over and over (naive Fibonacci computes fib(3) many times). Optimal substructure: the optimal answer is built from optimal answers to subproblems. When both hold, you compute each subproblem once and store it. That is the whole trick. Everything else is bookkeeping.

Memoization (top-down) vs tabulation (bottom-up)

Fibonacci, fixed two ways. Both turn O(2^n) into O(n).

python

# Top-down: recursion + a cache (memo). Write the natural recursion, add memory.
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Bottom-up: build a table from the smallest subproblems upward, no recursion.
def fib_tab(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]
# Both O(n) time. Bottom-up uses O(1) space if you keep only the last two values.

A real DP problem: coin change

Fewest coins to make an amount. Classic bottom-up DP.

python

def coin_change(coins, amount):
    # dp[a] = fewest coins to make amount a; infinity = impossible
    dp = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# coin_change([1,2,5], 11) -> 3  (5 + 5 + 1)
# Time O(amount * len(coins)). The subproblem: best for each smaller amount.

The thought process for spotting a DP problem

Interviewers grade your recognition, not memorized solutions.

1
1. Ask: can I describe the answer in terms of answers to smaller versions? (optimal substructure)
2
2. Ask: does a naive recursion solve the same subproblem repeatedly? (overlapping subproblems)
3
3. If yes to both, define the subproblem precisely (what does dp[i] mean?).
4
4. Write the recurrence (how dp[i] depends on smaller entries) and the base cases.
5
5. Choose top-down (recursion + memo, easier to derive) or bottom-up (table, often less memory).
6
6. Optimize space if only the last few entries are needed.

Common mistakes only experienced devs catch

Jumping to a table before defining what dp[i] actually means, then getting lost. Wrong or missing base cases (the most common DP bug). Using a mutable default argument as a memo across calls in Python (subtle shared-state bug). Reaching for DP when greedy or a simple loop suffices. Forgetting you can often reduce O(n) space to O(1) by keeping only the last few entries. Memoizing on an incomplete key, so different states collide in the cache.

←Recursion

Back to Algorithms

Greedy Algorithms→