Dynamic Programming in Python for Beginners

Dynamic programming (DP) sounds advanced, but the idea is simple: do not solve the same small problem twice. Break a big problem into smaller pieces, solve each piece once, write the answer down, and reuse it whenever the same piece comes up again. It turns a solution that takes years into one that takes milliseconds, and it is a favourite topic in coding interviews.

This guide explains when DP applies, the two ways to write it (top-down and bottom-up), and then works through the classics one by one: Fibonacci, grid paths, coin change, house robber, knapsack and the longest common subsequence. We count calls instead of seconds, so the results are the same on every computer. All the output shown is real.

When does DP apply?

Look for two properties:

• Overlapping subproblems. A plain recursive solution asks the same question again and again. (Naive Fibonacci in Recursion in Python Explained Simply is the standard example.)
• Optimal substructure. The best answer to the big problem uses the best answers to smaller versions of it. The best route to a city passes through the best route to the city before it.

Problems that ask for a minimum, maximum, count or “is it possible”, where you must make a choice at each step, are the usual suspects. If the choices are independent and a simple rule always works, a greedy approach may be enough (see the coin example below for when it is not).

Start with Fibonacci

The recursive Fibonacci needs an exponential number of calls, because it recomputes the same values. In the recursion post, we saw memoization fix that. The other route is bottom-up: start with the smallest values and work up to the one you want. Because each value needs only the previous two, you do not even need a table:

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr      # only the last two values are needed
    return curr

print(fib(10), fib(50))
print(fib(100))

Output

55 12586269025
354224848179261915075

A loop of about 100 steps, instead of billions of calls. This is dynamic programming in its smallest form: reuse what you already computed.

Top-down and bottom-up

Every DP solution can be written in either of two styles:

Learn both. Start with top-down because it is easier to get right, and switch to bottom-up when you need speed, or when you want to save memory.

Example: paths in a grid

A robot in the top-left corner of a grid can move only right or down. How many different paths reach the bottom-right corner? The number of paths to any cell is the number of paths to the cell above it plus the number of paths to the cell on its left. The plain recursion follows that directly, and the cached version is the same code with a decorator. Count the calls:

from functools import lru_cache

slow_calls = 0
fast_calls = 0

def paths_slow(r, c):
    global slow_calls
    slow_calls += 1
    if r == 1 or c == 1:
        return 1
    return paths_slow(r - 1, c) + paths_slow(r, c - 1)

@lru_cache(maxsize=None)
def paths_fast(r, c):
    global fast_calls
    fast_calls += 1
    if r == 1 or c == 1:
        return 1
    return paths_fast(r - 1, c) + paths_fast(r, c - 1)

print(paths_slow(10, 10), "paths, using", slow_calls, "calls")
print(paths_fast(10, 10), "paths, using", fast_calls, "calls")

Output

48620 paths, using 97239 calls
48620 paths, using 99 calls

The same answer with 97,239 calls against 99. A 10 x 10 grid has only about 100 different cells, so once each one has been computed there is nothing left to do. The bottom-up version fills a table of those cells, using the same rule:

def unique_paths(rows, cols):
    dp = [[1] * cols for _ in range(rows)]       # the first row and column have one path
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[-1][-1]

print(unique_paths(3, 7), unique_paths(10, 10))

Output

28 48620

Example: coin change

What is the fewest number of coins that add up to an amount? With coins of 1, 2 and 5 and an amount of 11, the answer is 3 (5 + 5 + 1). The state is “the fewest coins for this remaining amount”. The choice is which coin to use next, and we take the best over all of them. First, top-down, with the cache. (It uses the decorator from Python Decorators Explained.)

from functools import lru_cache

def min_coins(coins, amount):
    @lru_cache(maxsize=None)
    def best(rest):
        if rest == 0:
            return 0
        if rest < 0:
            return float("inf")
        return 1 + min(best(rest - c) for c in coins)

    result = best(amount)
    return -1 if result == float("inf") else result

print(min_coins((1, 2, 5), 11))
print(min_coins((2,), 3))

Output

3
-1

Bottom-up builds an array where dp[a] is the fewest coins for amount a, starting at dp[0] = 0. Printing the whole table shows how each amount is built from a smaller one:

def min_coins_table(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount                 # dp[a] = fewest coins that make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

print(min_coins_table([1, 2, 5], 11))
print(min_coins_table([2], 3))

dp = [min_coins_table([1, 2, 5], a) for a in range(12)]
print(dp)

Output

3
-1
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

For instance dp[11] = 3 because dp[10] = 2 (5 + 5) and one more coin of 1 makes 11. Why not just always take the biggest coin, the greedy way? Because it can be wrong:

def greedy(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else -1

print("greedy   :", greedy([1, 3, 4], 6))
print("dynamic  :", min_coins_table([1, 3, 4], 6))

Output

greedy   : 3
dynamic  : 2

With coins 1, 3 and 4 and an amount of 6, greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 uses only 2. DP tries every option, so it always finds the best one.

Example: house robber

A row of houses each holds some money, but you cannot rob two neighbouring houses. What is the most you can take? At each house you have a choice: skip it (keep the best so far) or rob it (its money plus the best from two houses back). So best[i] = max(best[i-1], best[i-2] + nums[i]). Only the last two values matter:

def rob(nums):
    prev2, prev1 = 0, 0        # best total two houses back, and one house back
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

print(rob([2, 7, 9, 3, 1]))
print(rob([1, 2, 3, 1]))
print(rob([]))

Output

12
4
0

For [2, 7, 9, 3, 1] the best is 2 + 9 + 1 = 12, and you never need a table.

Example: 0/1 knapsack

You have a bag that can hold a weight of 7, and items with a weight and a value each. Every item can be used at most once. What is the largest total value you can carry? For each item, either leave it or take it, and dp[w] stores the best value with weight limit w:

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)                    # dp[w] = best value with weight limit w
    for w, v in zip(weights, values):
        for cap in range(capacity, w - 1, -1):   # backwards, so each item is used once
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[capacity]

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))

Output

9

The best is the items weighing 3 and 4, worth 4 + 5 = 9. The inner loop runs backwards. This is the detail that matters: going forwards would let the same item be counted again in the same round, turning it into an “unlimited items” problem.

Example: longest common subsequence

A subsequence keeps the order of the letters but may skip some. What is the longest subsequence that two strings share? This is a two-dimensional problem, so the table has a row for each letter of one string and a column for each letter of the other. If the two letters match, extend the diagonal. If not, take the better of the cell above or the cell on the left:

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          # the letters match: extend
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp

table = lcs("abcde", "ace")
for label, row in zip(" " + "abcde", table):
    print(label, row)
print("longest common subsequence length:", table[-1][-1])
print(lcs("AGGTAB", "GXTXAYB")[-1][-1])

Output

  [0, 0, 0, 0]
a [0, 1, 1, 1]
b [0, 1, 1, 1]
c [0, 1, 2, 2]
d [0, 1, 2, 2]
e [0, 1, 2, 3]
longest common subsequence length: 3
4

The last cell holds the answer. "abcde" and "ace" share "ace", so it is 3. This is the algorithm behind diff tools that show what changed between two versions of a file, and it is also related to spell checkers and DNA comparison.

A recipe for any DP problem

1. Define the state. Say in words what dp[i] (or dp[i][j]) means. This is the hardest and most important step.
2. Write the recurrence. How does one entry come from smaller entries? (max of choices, a sum, or a match/no-match rule.)
3. Set the base cases. The entries you know without thinking, such as dp[0].
4. Choose the order. Smaller entries must be filled before the ones that use them.
5. Read the answer. Often the last cell, sometimes the maximum over the table.
6. Optimize memory if it matters: keep only the row or the two values you still need.

The time is usually the number of states times the work per state. Grid paths: rows x cols states, one addition each. Coin change: amount x coins. (See Big O Notation in Python for how to read that.)

Common mistakes

• Skipping the state definition. If you cannot say what dp[i] means, the recurrence will be wrong.
• Wrong base cases. Check the smallest inputs by hand: an empty list, amount 0, one item.
• Using DP where greedy is enough, or greedy where DP is needed. Test greedy on a small counterexample first, like the coin example.
• Filling the table in the wrong order. Every entry must only use entries that are already filled.
• Mutable defaults or shared rows. [[0] * n] * m makes all rows the same list. Use [[0] * n for _ in range(m)] (see Mutable vs Immutable in Python).
• Recursion limit. A deep top-down solution can hit it. Switch to bottom-up.

Try it yourself

Work out each answer first, then open the solution.

1. You can climb a staircase one or two steps at a time. In how many different ways can you climb n stairs?

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

print(climb(1), climb(2), climb(5), climb(10))

1 2 8 89

2. Count the number of different combinations of coins [1, 2, 5] that make 5 (order does not matter).

def count_ways(coins, amount):
    ways = [1] + [0] * amount          # one way to make 0: use no coins
    for c in coins:
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

print(count_ways([1, 2, 5], 5))

4

3. Find the length of the longest strictly increasing subsequence of [10, 9, 2, 5, 3, 7, 101, 18].

def lis(nums):
    best = [1] * len(nums)             # best[i] = longest increasing run ending at i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                best[i] = max(best[i], best[j] + 1)
    return max(best, default=0)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]), lis([]))

4 0

4. How can you tell that a problem probably needs dynamic programming?

Run these in our free Python compiler.

Frequently asked questions

What is dynamic programming in simple words?

It is a way of solving a problem by breaking it into smaller problems, solving each one only once, and saving the answers so they can be reused instead of recomputed.

What is the difference between memoization and tabulation?

Memoization (top-down) is recursion that caches its results. Tabulation (bottom-up) fills a table iteratively from the smallest case. They solve the same problems and have the same time complexity.

What is the difference between dynamic programming and recursion?

Plain recursion may solve the same subproblem many times. Dynamic programming stores each subproblem’s answer, so it is solved only once.

When should I use dynamic programming instead of greedy?

When a locally best choice can lead to a worse total, as with coins 1, 3, 4 and an amount of 6. If you can prove that the greedy choice is always safe, greedy is simpler and faster.

Is dynamic programming hard to learn?

It takes practice, but the steps are always the same: define the state, write the recurrence, set the base cases and choose the order. Start with Fibonacci, grid paths and coin change.

How do I do dynamic programming in Python?

Either add @lru_cache(maxsize=None) to a recursive function, or fill a list (or a list of lists) with a loop, using earlier entries to compute later ones.

Related reading

• Recursion in Python Explained Simply – where memoization starts.
• Backtracking in Python: Subsets and Permutations – when you must list the solutions, not count them.
• Big O Notation Explained With Python Examples – measuring the number of states.
• 10 Coding Interview Patterns in Python – DP among the other patterns.