Dynamic Programming — Core Concepts

Why dynamic programming matters

Dynamic programming (DP) solves problems that would otherwise take exponential time. It appears everywhere: route optimization, text comparison, resource allocation, game strategy, and machine learning. Recognizing when a problem is a DP problem — and knowing the patterns — is a core skill for any serious Python developer.

The two conditions for DP

A problem can be solved with DP when it has:

1. Optimal substructure — the optimal solution to the whole problem can be built from optimal solutions to its subproblems.
2. Overlapping subproblems — the same subproblems appear multiple times during recursion.

If your problem has both, DP applies. If subproblems do not overlap (each is solved only once), you have divide-and-conquer instead (like merge sort).

Top-down vs. bottom-up

Top-down (memoization)

Start with the original problem and recursively break it down, caching results:

from functools import lru_cache

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

Python’s @lru_cache makes top-down DP almost effortless. You write the recursive solution naturally and add one line for caching.

Bottom-up (tabulation)

Start from the smallest subproblems and build up 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]

Bottom-up avoids recursion depth limits and is usually faster due to less function call overhead. But the logic can be harder to develop because you must figure out the iteration order.

Classic DP patterns

The knapsack problem

You have items with weights and values, and a bag with a weight limit. Maximize the total value:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]  # skip item
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
    
    return dp[n][capacity]

Longest common subsequence (LCS)

Find the longest sequence of characters common to two strings (not necessarily contiguous):

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[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[m][n]

This is the foundation of diff tools and DNA sequence alignment.

Coin change (minimum coins)

Find the fewest coins that make a given amount:

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

Space optimization

Many DP problems only need the previous row to compute the current row. You can reduce O(n × m) space to O(m):

def knapsack_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):  # reverse to avoid reuse
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

The reverse iteration is critical — it ensures each item is used at most once.

How to identify DP problems

Look for these signals:

• “Find the minimum/maximum…”
• “Count the number of ways…”
• “Is it possible to…?”
• Choices at each step that affect future options
• The problem can be expressed as a function of smaller inputs

Common misconception

“DP is just recursion with caching.” Memoization is one form of DP, but bottom-up tabulation, space optimization, and recognizing the right state representation are equally important skills. The hardest part of DP is not the caching — it is defining the right subproblem.

One thing to remember: The key to DP is asking “what information do I need to make the next decision?” That answer becomes your state, and everything else follows from there.