DevPath
Tracks

Dynamic Programming

Solve a problem by breaking it into overlapping sub-problems and remembering each answer. Top-down vs bottom-up, coin change, LCS, and knapsack.

advanced55 min#dynamic-programming#memoization#tabulation#optimization

Prerequisites: Recursion, Arrays and Dynamic Arrays

Why it matters

Dynamic programming (DP) turns problems that look exponential into polynomial ones. Route planning, spell correction (edit distance), diffing files (longest common subsequence), resource allocation, and text layout all rely on it. It also has a reputation as the hardest interview topic, mostly because people memorize solutions instead of learning the method for finding the state. The method is learnable.

Intuition

Suppose you are asked for the fewest coins that make 10 using coins 1, 5 and 6. If you already knew the answer for 9, for 5, and for 4, you would just add one coin to the best of them. And to know the answer for 9 you would ask the same question again for smaller amounts. A naive recursion asks about the same amounts over and over, a tree of repeated work. DP says: compute each distinct question once, write the answer down, and reuse it.

A picture of the repeated work, using the Fibonacci recursion fib(4), where each call asks for the two before it.

f4f3f2 #1f1 #1f0 #1f1 #2f2 #2f1 #3f0 #2
f2 is computed twice (green and amber subtrees are identical), and f1 three times. With memoization the amber subtree vanishes: the second f2 is just a lookup. For fib(40) this duplication explodes into hundreds of millions of calls.

Two properties must hold:

  • Overlapping sub-problems: the same smaller questions recur. (If they never repeat, plain divide and conquer is enough.)
  • Optimal substructure: the best answer to the big problem is built from best answers to smaller ones.

How it works

Finding the state is the real skill. Ask: what is the smallest set of numbers that fully describes "where I am" in the problem, so that the future depends only on it?

  • Coin change: the remaining amount. state = (rem).
  • Longest common subsequence: how much of each string is consumed. state = (i, j).
  • 0/1 knapsack: which item we are deciding on and remaining capacity. state = (item, cap).

Then write the recurrence: how does the answer for a state follow from smaller states? For coin change, best(rem) = 1 + min(best(rem - c) for each coin c). Finally set the base cases (best(0) = 0) and decide the order.

There are two equivalent ways to evaluate.

Top-down (memoization): write the natural recursion, then cache results by state. Easy to derive and only computes the states actually reached. Cost: recursion depth and call overhead.

Bottom-up (tabulation): fill a table from the smallest states up so that every dependency is ready when needed. No recursion, easy to optimize memory. Cost: you must get the order right.

The same idea with the intro example, fewest coins to make 10 using coins 1, 5 and 6, as a one-dimensional table.

0
0
1
2
3
4
5
6
7
8
9
10
dp[x] is the fewest coins to make x, coins 1, 5, 6. Base case: dp[0] = 0, no coins make 0.
step 1 / 7

The index under each cell is the amount. Each cell looks back at dp[x - coin] for every coin and keeps the smallest result plus one.

LCS table for "ABC" vs "AC"        "" A  C
                              ""    0  0  0
                              A     0  1  1
                              B     0  1  1
                              C     0  1  2
Match: take diagonal + 1. Otherwise: max(up, left).

Here is the "ABC" versus "AC" table from above, filled one cell at a time. Green is the cell being computed, amber are the cells it reads.

(empty)AC
(empty)
0
0
0
A
0
B
0
C
0
Base row and column: an empty string has LCS 0 with anything. Now fill the rest, row by row.
step 1 / 7

Every cell is computed from at most three neighbours that are already filled. That fixed fill order is what makes bottom-up work.

Space optimization. If a row depends only on the previous row (or a state depends only on earlier cells of one array), keep just that. The knapsack below uses a single array and loops capacity backwards so each item is used at most once. Loop forwards and you accidentally allow unlimited copies (the unbounded knapsack, which is a different problem).

OperationTimeNotes
Naive recursion (coin change)ExponentialRecomputes the same amounts
Coin change, DPO(amount * coins)One cell per amount, one try per coin
LCS of lengths m and nO(m * n)Table size; O(min(m, n)) space possible
0/1 knapsackO(items * capacity)Pseudo-polynomial in the capacity value
Memoization overheadO(states) spacePlus recursion depth for top-down

Code: coin change, LCS, knapsack

from functools import lru_cache
 
def coin_change_top_down(coins, amount):
    @lru_cache(maxsize=None)
    def best(rem):                      # fewest coins to make rem
        if rem == 0:
            return 0
        if rem < 0:
            return float("inf")
        return 1 + min(best(rem - c) for c in coins)
    ans = best(amount)
    return -1 if ans == float("inf") else ans
 
def coin_change_bottom_up(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount           # dp[x] = fewest coins for x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
    return -1 if dp[amount] == INF else dp[amount]
 
def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[-1][-1]
 
def knapsack(weights, values, cap):
    dp = [0] * (cap + 1)                # dp[w] = best value with capacity w
    for wt, val in zip(weights, values):
        for w in range(cap, wt - 1, -1):  # backwards: each item used once
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[cap]
 
print(coin_change_top_down((1, 5, 6), 10), coin_change_bottom_up((1, 5, 6), 10))
print(coin_change_bottom_up((2,), 3))
print(lcs("ABCBDAB", "BDCABA"))
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))

Both versions print four lines: 2 2 (top-down and bottom-up agree: 5 + 5), -1 (3 cannot be made from coin 2), 4 (the LCS of "ABCBDAB" and "BDCABA" has length 4), and 9 (best knapsack value at capacity 7, taking the weights 3 and 4).

Common pitfalls

  • Wrong or incomplete state: if the answer also depends on something not in your state (like whether you used a skip yesterday), add it to the state.
  • Wrong iteration order: bottom-up needs every dependency computed before use. Loop capacity backwards for 0/1 knapsack, forwards for unbounded.
  • Mutable default cache or shared memo: reusing a memo across calls with different inputs (like different coin lists) returns stale answers.
  • Using infinity carelessly: inf + 1 is fine in both Python and JavaScript, but sentinel integers like 10**9 can overflow in other languages. Always convert an unreachable result to a clear answer such as -1.
  • Assuming greedy works: with coins 1, 5, 6 and amount 10, greedy takes 6 and four 1s (5 coins) while DP finds 5 + 5 (2 coins).
  • Recursion limit: Python's default depth is about 1000. Prefer bottom-up for deep problems.

Practice

Climbing stairs easy

Hint

To reach step n you came from step n-1 or n-2. Does that look familiar?

Show solution

ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1. This is the Fibonacci recurrence. Bottom-up with two variables gives O(n) time and O(1) space.

House robber medium

Hint

At each house you either skip it or rob it and skip the previous one.

Show solution

Let best[i] be the most money from the first i houses. Then best[i] = max(best[i - 1], best[i - 2] + money[i - 1]). Only the last two values matter, so keep two variables. O(n) time, O(1) space.

Edit distance medium

Hint

State is (i, j): prefixes of the two words. There are three operations to consider on a mismatch.

Show solution

dp[i][j] is the fewest edits to turn the first i characters of a into the first j of b. If the characters match, copy dp[i-1][j-1]. Otherwise it is 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)). Base cases are dp[i][0] = i and dp[0][j] = j. O(m * n).

Partition equal subset sum hard

Hint

If the total is odd the answer is no. Otherwise it is a yes/no knapsack with target total / 2.

Show solution

Use a boolean array reach of size target + 1 with reach[0] = true. For each number, loop s from target down to the number and set reach[s] = reach[s] or reach[s - num]. Answer is reach[target]. O(n * target) time, O(target) space.

Interview questions

  1. How do you tell a problem needs DP? It asks for a count, a minimum or maximum, or a yes/no over choices, and a brute-force recursion would repeat the same sub-calls.
  2. Top-down or bottom-up? Top-down is quicker to write and skips unreachable states; bottom-up avoids recursion limits and enables rolling arrays. Both have the same asymptotic time.
  3. What is the difference between DP and greedy? Greedy commits to one local choice and never reconsiders. DP considers all choices for each sub-problem and keeps the best, so it is slower but correct on more problems.
  4. Why is knapsack called pseudo-polynomial? Its runtime depends on the numeric value of the capacity, not just the number of bits needed to write it down.

Interviewers look for: a clearly stated state and recurrence before any code, correct base cases, and an explicit complexity of states times transitions.

Quick check

In the single-array 0/1 knapsack, why do we loop the capacity from high to low for each item?

Finished this lesson?

Further resources

Related lessons