Dynamic programming is one of the most powerful algorithmic techniques for solving optimization problems. If you have ever been stuck on a coding interview question or struggled with slow recursive solutions, dynamic programming is the skill that will transform your problem-solving ability.

In this comprehensive guide, you will learn exactly what dynamic programming is, when and how to apply it, and how to solve classic DP problems in Python with working code you can run immediately in our compiler.

What Is Dynamic Programming?

Dynamic programming (DP) is an algorithmic technique that solves complex problems by breaking them down into simpler subproblems. Instead of recomputing the same subproblems repeatedly, DP stores the results of each subproblem so they are computed only once.

Think of it like this: if you were asked to calculate fib(5), a naive recursive approach would compute fib(3) three separate times. Dynamic programming eliminates this redundancy by caching results.

The two key properties that make a problem suitable for DP are:

Optimal Substructure — The optimal solution to the problem can be constructed from optimal solutions of its subproblems.
Overlapping Subproblems — The same subproblems are solved multiple times in a recursive approach.

If a problem has both properties, dynamic programming will almost always give you a more efficient solution than plain recursion.

Top-Down vs Bottom-Up Approaches

There are two fundamental strategies for implementing dynamic programming in Python: top-down (memoization) and bottom-up (tabulation).

Top-Down: Memoization

Memoization starts from the original problem and recursively breaks it down into subproblems. As each subproblem is solved, its result is stored in a dictionary or array. When the same subproblem is encountered again, the cached result is returned instead of recomputing it.

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(10))  # 55
print(fibonacci_memo(50))  # 12586269025

Bottom-Up: Tabulation

Tabulation builds the solution iteratively from the smallest subproblems up to the original problem. It fills a table (usually an array) in a specific order, using previously computed values to solve larger subproblems.

def fibonacci_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]

print(fibonacci_tab(10))   # 55
print(fibonacci_tab(50))   # 12586269025

Which Approach Should You Use?

Approach	Pros	Cons	Best For
Memoization (Top-Down)	Intuitive, easier to write	Recursive overhead, stack limit	When only a fraction of subproblems need solving
Tabulation (Bottom-Up)	No recursion overhead, iterative	Requires figuring out fill order	When most/all subproblems need solving

In practice, bottom-up tabulation is often preferred in interviews because it avoids recursion depth issues and is generally faster in Python.

Classic DP Problems in Python

Let us walk through the most important dynamic programming problems you will encounter in interviews and real-world applications. Each example includes working code you can run in our compiler.

1. Climbing Stairs

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

This is essentially the Fibonacci sequence — to reach step n, you either came from step n-1 (one step) or step n-2 (two steps).

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# Space-optimized version
def climb_stairs_optimized(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

print(climb_stairs(5))           # 8
print(climb_stairs_optimized(5)) # 8

Time Complexity: O(n) Space Complexity: O(n) for tabulation, O(1) for optimized version

2. 0/1 Knapsack Problem

Given a set of items, each with a weight and a value, determine which items to include in a knapsack so that the total weight does not exceed a given capacity and the total value is maximized.

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = max value using items 0..i with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Don't take item i
            dp[i][w] = dp[i - 1][w]
            # Take item i if it fits
            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]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack(weights, values, capacity))  # 10

Time Complexity: O(n * capacity) Space Complexity: O(n * capacity)

3. Longest Common Subsequence (LCS)

Given two strings, find the length of the longest subsequence present in both. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously.

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[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]

print(lcs("abcde", "ace"))    # 3
print(lcs("abc", "def"))      # 0

Time Complexity: O(m * n) Space Complexity: O(m * n)

4. Coin Change Problem

Given an array of coin denominations and a target amount, find the minimum number of coins needed to make the amount. If it is not possible, return -1.

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

coins = [1, 5, 10, 25]
amount = 30
print(coin_change(coins, amount))  # 2 (25 + 5)

coins = [2]
amount = 3
print(coin_change(coins, amount))  # -1

Time Complexity: O(amount * len(coins)) Space Complexity: O(amount)

5. Edit Distance

Given two strings, find the minimum number of operations (insert, delete, replace) required to convert one string to the other.

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                    dp[i - 1][j - 1]   # replace
                )

    return dp[m][n]

print(edit_distance("kitten", "sitting"))  # 3
print(edit_distance("intention", "execution"))  # 5

Time Complexity: O(m * n) Space Complexity: O(m * n)

6. Maximum Subarray (Kadane’s Algorithm)

Find the contiguous subarray with the largest sum. This is a classic 1D DP problem.

def max_subarray(nums):
    max_sum = nums[0]
    current_sum = nums[0]

    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
print(max_subarray([1]))  # 1

Time Complexity: O(n) Space Complexity: O(1)

7. Longest Increasing Subsequence (LIS)

Find the length of the longest strictly increasing subsequence in an array.

import bisect

def lis(nums):
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
print(lis([0, 1, 0, 3, 2, 3]))  # 4

Time Complexity: O(n log n) Space Complexity: O(n)

DP Patterns to Recognize

Learning to identify which pattern applies to a new problem is the hardest part of dynamic programming. Here are the most common patterns:

1D DP

Use when the state depends on a single variable (usually an index or position).

Climbing Stairs
House Robber
Maximum Subarray
Fibonacci Sequence

2D DP

Use when the state depends on two variables (usually two indices in strings or arrays).

Longest Common Subsequence
Edit Distance
0/1 Knapsack
Unique Paths in a Grid

DP on Strings

A subset of 2D DP where you compare or transform strings.

Edit Distance
Longest Common Subsequence
Longest Palindromic Subsequence
Word Break

DP on Trees

Use when the problem involves tree structures and you need to compute something for every subtree.

Diameter of a Binary Tree
Maximum Path Sum
Tree Diameter

Time and Space Complexity Analysis

Understanding the complexity of your DP solutions is critical for interviews and production code.

General approach to analyze DP complexity:

Count the number of unique subproblems
Determine the work done per subproblem
Total time = number of subproblems × work per subproblem
Space = typically the size of your DP table

Problem	Time	Space
Fibonacci	O(n)	O(1) optimized, O(n) tabulation
0/1 Knapsack	O(n × W)	O(n × W)
LCS	O(m × n)	O(m × n)
Coin Change	O(amount × coins)	O(amount)
Edit Distance	O(m × n)	O(m × n)
Kadane’s	O(n)	O(1)
LIS	O(n log n)	O(n)

Common Mistakes to Avoid

Forgetting base cases — Every DP solution needs a base case. Without it, your function will recurse infinitely or produce incorrect results.
Using recursion without memoization — Plain recursion on DP problems leads to exponential time complexity. Always cache results.
Wrong recursion order — In top-down DP, make sure you call subproblems before using their results. In bottom-up, fill the table in the correct direction.
Not considering space optimization — Many 2D DP problems can be reduced to O(n) or O(1) space if you only need the previous row. For example, the Fibonacci sequence can use just two variables.
Off-by-one errors — When creating DP tables, carefully consider whether to use n+1 size and how indices map to problem states.
Ignoring the state definition — Clearly define what dp[i] or dp[i][j] represents before writing transitions. A vague state definition leads to incorrect solutions.

Practice Problems

Work through these problems in order of difficulty. Each one reinforces a different DP pattern.

Fibonacci Number (Easy) — Classic warm-up. Implement both memoization and tabulation.
Climbing Stairs (Easy) — 1D DP. Very similar to Fibonacci.
Minimum Cost Climbing Stairs (Easy) — 1D DP with costs at each step.
House Robber (Medium) — 1D DP with constraints (cannot rob adjacent houses).
Coin Change (Medium) — Classic unbounded knapsack variant.
Longest Increasing Subsequence (Medium) — 1D DP or binary search optimization.
0/1 Knapsack (Medium) — Foundational 2D DP problem.
Longest Common Subsequence (Medium) — Foundational 2D DP on strings.
Edit Distance (Medium) — 2D DP with three possible transitions.
Word Break (Medium) — 1D DP combined with string matching.

Key Takeaways

Dynamic programming solves problems by breaking them into overlapping subproblems with optimal substructure
Memoization (top-down) uses recursion with caching; tabulation (bottom-up) fills a table iteratively
Tabulation is generally preferred in Python due to no recursion depth limits
Recognizing the DP pattern (1D, 2D, on strings, on trees) is the key skill to develop
Always define your state clearly before writing the recurrence relation
Practice the 10 problems above until you can solve them without looking at solutions

Run every code example above in our compiler to see the output instantly. Modify the inputs and observe how the results change — this hands-on practice is the fastest way to master dynamic programming.

Frequently Asked Questions

What is dynamic programming in simple terms?

Dynamic programming is an algorithmic technique that solves complex problems by breaking them into simpler subproblems, solving each subproblem only once, and storing the results. It eliminates redundant computation that occurs in naive recursive solutions, typically reducing exponential time complexity to polynomial time.

When should I use dynamic programming instead of recursion?

Use dynamic programming when a recursive solution has overlapping subproblems — meaning the same subproblem is solved multiple times. If a recursive solution does not recompute anything, plain recursion (or divide and conquer) is sufficient. Common indicators: the problem asks for “minimum,” “maximum,” “number of ways,” or “is it possible.”

What is the difference between memoization and tabulation?

Memoization (top-down) starts with the original problem and recursively solves subproblems, caching results as they are computed. Tabulation (bottom-up) iteratively fills a table starting from the smallest subproblems. Tabulation avoids recursion overhead and stack overflow risks, while memoization is often easier to implement when not all subproblems need solving.

How do I identify if a problem can be solved with dynamic programming?

Look for two properties: (1) Optimal substructure — the optimal solution contains optimal solutions to subproblems. (2) Overlapping subproblems — the same subproblems appear multiple times. If both exist, DP is applicable. Problems asking for counts, minimums, maximums, or boolean possibilities on sequences are strong candidates.

What are the most common DP patterns I should learn?

The four essential patterns are: (1) 1D DP — state depends on a single index (e.g., climbing stairs, house robber), (2) 2D DP — state depends on two indices (e.g., LCS, edit distance), (3) Knapsack variants — 0/1 knapsack, unbounded knapsack, subset sum, and (4) DP on strings — comparing or transforming strings with 2D tables.

How much space can I save with space optimization?

Many 2D DP problems only need the previous row, allowing you to reduce space from O(m × n) to O(n). Some 1D problems can be reduced to O(1) space by keeping only the last two values (like Fibonacci). Always check if your recurrence only depends on a small window of previous states.