Dynamic Programming (DP) is one of those topics that can feel intimidating to many developers. It’s often associated with complex interview problems and deep algorithmic thinking. But at its core, DP is a powerful technique for solving certain types of optimization problems by breaking them down into simpler, overlapping subproblems and storing the results.

This post aims to provide a clear, practical introduction to DP. We’ll cover the fundamental principles, the two main approaches, and walk through concrete examples you can run yourself.

What is Dynamic Programming?

Dynamic Programming is an algorithmic technique for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, we look up the already computed solution instead of recomputing it.

This approach is highly effective for problems exhibiting two key characteristics:

1. Optimal Substructure: An optimal solution to the problem can be constructed from optimal solutions to its subproblems.
2. Overlapping Subproblems: The same subproblems are encountered and solved repeatedly.

If a problem has these two properties, DP is likely a suitable approach. Without overlapping subproblems, a simple divide-and-conquer strategy (like Merge Sort) might be more appropriate. Without optimal substructure, DP won’t guarantee an optimal solution for the larger problem.

The Problem with Naive Recursion

Let’s take the classic Fibonacci sequence as an example. The n-th Fibonacci number F(n) is defined as F(n) = F(n-1) + F(n-2), with base cases F(0) = 0 and F(1) = 1.

A naive recursive implementation might look like this:

# fibonacci_naive.py
def fibonacci_naive(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

print(f"F(0) = {fibonacci_naive(0)}")
print(f"F(1) = {fibonacci_naive(1)}")
print(f"F(5) = {fibonacci_naive(5)}")
print(f"F(10) = {fibonacci_naive(10)}")

F(0) = 0
F(1) = 1
F(5) = 5
F(10) = 55

While correct, this approach is extremely inefficient for larger n. To compute F(5), it computes F(4) and F(3). F(4) in turn computes F(3) and F(2). Notice that F(3) is computed twice. This redundancy grows exponentially. For F(50), you’d be recomputing F(48) and F(47) countless times. This is the overlapping subproblems issue in action.

Two Approaches to Dynamic Programming

There are two primary ways to implement a DP solution:

1. Memoization (Top-Down DP): This is a recursive approach that stores the results of expensive function calls and returns the cached result when the same inputs occur again. It starts from the problem you want to solve and recursively breaks it down.
2. Tabulation (Bottom-Up DP): This is an iterative approach that builds up solutions to subproblems from the base cases. It typically involves filling a DP table (array or list) in a specific order.

Let’s see how both apply to the Fibonacci problem.

1. Memoization (Top-Down)

Memoization is essentially recursion with a cache. You use a data structure (like a dictionary or array) to store the results of subproblems. Before computing F(n), you check if it’s already in your cache. If yes, return the cached value. If no, compute it, store it, and then return it.

# fibonacci_memoized.py
def fibonacci_memoized(n: int, memo: dict[int, int] = None) -> int:
    if memo is None:
        memo = {} # Initialize memo on the first call

    if n <= 1:
        return n
    
    if n in memo:
        return memo[n]
    
    result = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
    memo[n] = result
    return result

print(f"F(0) = {fibonacci_memoized(0)}")
print(f"F(1) = {fibonacci_memoized(1)}")
print(f"F(5) = {fibonacci_memoized(5)}")
print(f"F(10) = {fibonacci_memoized(10)}")
print(f"F(50) = {fibonacci_memoized(50)}") # Now this is fast!

F(0) = 0
F(1) = 1
F(5) = 5
F(10) = 55
F(50) = 12200160415121876738

Note: Python’s functools.lru_cache decorator provides a convenient way to add memoization to functions automatically.

# fibonacci_lru_cache.py
from functools import lru_cache

@lru_cache(maxsize=None) # maxsize=None means unlimited cache size
def fibonacci_lru(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci_lru(n - 1) + fibonacci_lru(n - 2)

print(f"F(0) = {fibonacci_lru(0)}")
print(f"F(1) = {fibonacci_lru(1)}")
print(f"F(5) = {fibonacci_lru(5)}")
print(f"F(10) = {fibonacci_lru(10)}")
print(f"F(50) = {fibonacci_lru(50)}")

F(0) = 0
F(1) = 1
F(5) = 5
F(10) = 55
F(50) = 12200160415121876738

2. Tabulation (Bottom-Up)

Tabulation removes recursion entirely. It builds the solution iteratively from the base cases up to the desired n. You typically use an array (or list in Python) to store the computed values.

# fibonacci_tabulated.py
def fibonacci_tabulated(n: int) -> int:
    if n <= 1:
        return n
    
    # Create a DP table to store results
    # dp[i] will store F(i)
    dp = [0] * (n + 1)
    
    # Base cases
    dp[0] = 0
    dp[1] = 1
    
    # Fill the DP table iteratively
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
        
    return dp[n]

print(f"F(0) = {fibonacci_tabulated(0)}")
print(f"F(1) = {fibonacci_tabulated(1)}")
print(f"F(5) = {fibonacci_tabulated(5)}")
print(f"F(10) = {fibonacci_tabulated(10)}")
print(f"F(50) = {fibonacci_tabulated(50)}") # Also fast!

F(0) = 0
F(1) = 1
F(5) = 5
F(10) = 55
F(50) = 12200160415121876738

Which one to choose?

• Memoization (Top-Down): Often more intuitive to translate from a recursive definition. Can be easier to implement for problems with complex state transitions or when only a subset of subproblems needs to be solved. Can lead to stack overflow for very large inputs due to deep recursion.
• Tabulation (Bottom-Up): Generally avoids recursion overhead and stack overflow issues, making it slightly more efficient in some cases. Requires careful thought about the order in which the DP table should be filled. Sometimes harder to derive if the dependencies are complex.

Note: For Fibonacci, the state dp[i] only depends on dp[i-1] and dp[i-2]. This means we don’t even need the full dp array; we can optimize space to O(1) by just keeping track of the last two values.

# fibonacci_space_optimized.py
def fibonacci_space_optimized(n: int) -> int:
    if n <= 1:
        return n
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
        
    return b

print(f"F(0) = {fibonacci_space_optimized(0)}")
print(f"F(1) = {fibonacci_space_optimized(1)}")
print(f"F(5) = {fibonacci_space_optimized(5)}")
print(f"F(10) = {fibonacci_space_optimized(10)}")
print(f"F(50) = {fibonacci_space_optimized(50)}")

F(0) = 0
F(1) = 1
F(5) = 5
F(10) = 55
F(50) = 12200160415121876738

This space optimization is possible when a subproblem’s solution only depends on a few “immediately preceding” subproblems, rather than the entire history.

A More Involved Example: Coin Change Problem

This is a classic DP problem that demonstrates more complex state management.

Problem: Given an array of coin denominations coins and a target amount amount, find the fewest number of coins that you need to make up that amount. If that amount cannot be made up by any combination of the coins, return -1. Assume you have an infinite number of each kind of coin.

Example: coins = [1, 2, 5], amount = 11 Output: 3 (11 = 5 + 5 + 1)

Optimal Substructure: The minimum coins for amount is 1 + min_coins(amount - coin_value) for all coin_value in coins. Overlapping Subproblems: Calculating min_coins(k) might be required multiple times for different paths to amount.

Let’s try both memoization and tabulation.

1. Coin Change (Memoization - Top-Down)

# coin_change_memoized.py
def coin_change_memoized(coins: list[int], amount: int) -> int:
    # memo stores the minimum coins needed for a given amount
    memo = {}

    def dp(rem: int) -> int:
        if rem == 0:
            return 0  # 0 coins needed for 0 amount
        if rem < 0:
            return float('inf') # Invalid state, cannot make amount
        
        if rem in memo:
            return memo[rem]
        
        min_coins_for_rem = float('inf')
        for coin in coins:
            # Try to use current coin and find min for remaining amount
            res = dp(rem - coin)
            if res != float('inf'): # If a solution exists for rem - coin
                min_coins_for_rem = min(min_coins_for_rem, 1 + res)
        
        memo[rem] = min_coins_for_rem
        return min_coins_for_rem

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

# Test cases
print(f"Coins: [1,2,5], Amount: 11 -> {coin_change_memoized([1,2,5], 11)}")
print(f"Coins: [2], Amount: 3 -> {coin_change_memoized([2], 3)}")
print(f"Coins: [1], Amount: 0 -> {coin_change_memoized([1], 0)}")
print(f"Coins: [186,419,83,408], Amount: 6249 -> {coin_change_memoized([186,419,83,408], 6249)}")

Coins: [1,2,5], Amount: 11 -> 3
Coins: [2], Amount: 3 -> -1
Coins: [1], Amount: 0 -> 0
Coins: [186,419,83,408], Amount: 6249 -> 20

Explanation:

• The dp(rem) function calculates the minimum coins for the remaining rem amount.
• Base cases:
  • rem == 0: We’ve reached the target with 0 additional coins.
  • rem < 0: This path is invalid (over-shot the amount). Return inf to signify impossibility.
• Memoization: if rem in memo: return memo[rem].
• Recurrence: min_coins_for_rem = min(min_coins_for_rem, 1 + dp(rem - coin)). We iterate through all coins, assume we use one of them, and add 1 to the minimum coins needed for the reduced amount. We take the minimum across all coin choices.
• Finally, if the result is still inf, it means the amount cannot be made.

2. Coin Change (Tabulation - Bottom-Up)

# coin_change_tabulated.py
def coin_change_tabulated(coins: list[int], amount: int) -> int:
    # dp[i] will store the minimum number of coins to make amount 'i'
    # Initialize dp table with infinity for all amounts, except dp[0]
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 coins needed for 0 amount

    # Iterate through each amount from 1 to 'amount'
    for i in range(1, amount + 1):
        # For each amount 'i', try every coin
        for coin in coins:
            # If the current coin can be used to form amount 'i'
            # (i.e., 'i - coin' is a valid non-negative amount)
            if i - coin >= 0:
                # Update dp[i] with the minimum of its current value
                # and 1 (for the current coin) + dp[i - coin]
                # (for the remaining amount)
                dp[i] = min(dp[i], 1 + dp[i - coin])

    # If dp[amount] is still infinity, it means amount cannot be made
    return dp[amount] if dp[amount] != float('inf') else -1

# Test cases
print(f"Coins: [1,2,5], Amount: 11 -> {coin_change_tabulated([1,2,5], 11)}")
print(f"Coins: [2], Amount: 3 -> {coin_change_tabulated([2], 3)}")
print(f"Coins: [1], Amount: 0 -> {coin_change_tabulated([1], 0)}")
print(f"Coins: [186,419,83,408], Amount: 6249 -> {coin_change_tabulated([186,419,83,408], 6249)}")

Coins: [1,2,5], Amount: 11 -> 3
Coins: [2], Amount: 3 -> -1
Coins: [1], Amount: 0 -> 0
Coins: [186,419,83,408], Amount: 6249 -> 20

Explanation:

• Initialize dp array: dp[0] is 0, all others are inf.
• Outer loop: for i in range(1, amount + 1): We compute dp[i] for each i from 1 up to amount. This ensures that when we calculate dp[i], all dp[i - coin] values (which are for smaller amounts) have already been computed.
• Inner loop: for coin in coins: For each amount i, we consider using each coin.
• Update rule: dp[i] = min(dp[i], 1 + dp[i - coin]). This is the core. It means “to make amount i, I can either use one of the minimum ways found so far, OR I can use this coin and add it to the minimum way to make i - coin.”

This approach is generally preferred for its iterative nature, which avoids recursion depth limits and sometimes offers better performance due to less overhead.

Identifying DP Problems and Common Patterns

While DP problems can seem daunting, with practice, you start to spot patterns:

1. Optimization Problems: “Find the maximum/minimum…”, “What’s the longest/shortest…”, “Least/most number of ways…”
2. Counting Problems: “How many ways can you…”.
3. Range-based Problems: Solutions that depend on sub-ranges (e.g., matrix chain multiplication, longest palindromic subsequence).
4. Knapsack-like Problems: Choosing items with weights/values to maximize value within a capacity.

Tips for Solving DP Problems:

• Define the “State”: What are the variables that uniquely identify a subproblem? For Coin Change, it’s the amount remaining. For path problems, it might be (row, col).
• Identify the Base Cases: What are the smallest, simplest subproblems whose solutions are known? (e.g., F(0)=0, dp[0]=0 for coin change).
• Write Down the Recurrence Relation: How does the solution to a larger problem depend on the solutions to smaller subproblems? This is often the hardest part. Try to express DP(state) in terms of DP(smaller_state).
• Choose an Approach (Memoization or Tabulation):
  • Memoization: Easier if the recurrence is complex or you don’t know the exact order to compute subproblems.
  • Tabulation: Good for simpler recurrences where dependencies are clear, and generally avoids recursion depth issues.
• Consider Space Optimization: Can you reduce the space complexity if current state only depends on a few previous states (like O(1) Fibonacci)?

Conclusion

Dynamic Programming is a powerful and elegant technique for solving a specific class of problems efficiently. It’s not magic; it’s a systematic way of avoiding redundant computations. The key lies in identifying overlapping subproblems and optimal substructure, then choosing between top-down memoization or bottom-up tabulation.

Don’t be discouraged if DP problems don’t click immediately. They require practice. Start with simple problems like Fibonacci, then move to Coin Change, Knapsack, and Longest Common Subsequence. The more you recognize the patterns and apply the two core approaches, the more natural DP will become. Good luck!