The 5 Dynamic Programming Patterns That Solve 90% of DP Problems

Dynamic programming has a reputation for being the hardest topic in coding interviews. And honestly, if you approach it as "each problem is unique and requires a flash of insight," it is hard. But here's the thing most tutorials won't tell you: the vast majority of DP problems fall into about five patterns. Learn those patterns, recognize which one applies, and the "flash of insight" becomes mechanical.

This guide covers the five patterns that solve roughly 90% of the DP problems you'll encounter in interviews. For each, I'll show you the core idea, the template, classic examples, and common variations.

Before We Start: The DP Mindset

Every DP problem has two ingredients:

1. Optimal substructure — the optimal solution to the problem contains optimal solutions to subproblems.
2. Overlapping subproblems — the same subproblems are solved multiple times.

The approach is always the same: define the state (what information do you need to describe a subproblem?), write the recurrence (how does a subproblem relate to smaller subproblems?), and decide on the base case (what's the smallest subproblem you can solve directly?).

Top-down (memoization) and bottom-up (tabulation) are just two ways to implement the same recurrence. Use whichever feels more natural — in interviews, top-down is often easier to write quickly, while bottom-up is easier to optimize for space.

Pattern 1: 0/1 Knapsack

The setup: You have a set of items, each with a weight and a value. You have a capacity constraint. You want to maximize value without exceeding capacity. Each item can be used at most once. State: dp[i][w] = maximum value achievable using the first i items with capacity w. Recurrence: For each item, you either include it or skip it.

dp[i][w] = max(
    dp[i-1][w],                           # skip item i
    dp[i-1][w - weight[i]] + value[i]     # include item i (if weight[i] <= w)
)

Base case: dp[0][w] = 0 for all w (no items, no value).

Template

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

Time: O(n capacity). Space: O(n capacity), reducible to O(capacity) by using a 1D array and iterating capacity in reverse.

Space-Optimized Version

def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):  # reverse order!
            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. If you iterate forward, you'd use the updated values from the current row, effectively allowing items to be reused (which is the unbounded knapsack pattern).

Classic Problems

Subset Sum: Given a set of numbers and a target, can you find a subset that sums to the target? This is 0/1 knapsack where value = weight = each number, and you're asking "can I fill the knapsack exactly?"

def can_partition(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True

for num in nums:
        for t in range(target, num - 1, -1):
            dp[t] = dp[t] or dp[t - num]

return dp[target]

Partition Equal Subset Sum: Can you split an array into two subsets with equal sum? Compute total sum. If odd, impossible. If even, find a subset summing to total/2. Reduces directly to subset sum. Target Sum: Given numbers and a target, assign + or - to each number to reach the target. This reduces to: find a subset summing to (total + target) / 2. Count of Subset Sum: Same as subset sum, but count how many subsets sum to the target. Change or to +.

When to Recognize It

You have a collection of items. You pick or skip each one. There's a constraint on what you can pick. You want to optimize something. That's 0/1 knapsack.

Pattern 2: Longest Common Subsequence (LCS)

The setup: Given two sequences, find the longest subsequence common to both. A subsequence doesn't need to be contiguous. State: dp[i][j] = length of LCS of the first i characters of string A and first j characters of string B. Recurrence:

if A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1        # characters match, extend LCS
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one character from either string

Base case: dp[0][j] = dp[i][0] = 0.

Template

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

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

Time: O(m n). Space: O(m n), reducible to O(min(m, n)) with a rolling array.

Classic Problems

Edit Distance (Levenshtein Distance): Minimum insertions, deletions, and replacements to convert one string to another. Same state as LCS, but the recurrence handles three operations:

def edit_distance(a, b):
    m, n = len(a), len(b)
    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 a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],      # delete from a
                    dp[i][j-1],      # insert into a
                    dp[i-1][j-1]     # replace
                )

return dp[m][n]

Longest Common Substring: Same as LCS, but the subsequence must be contiguous. If characters don't match, reset to 0 instead of taking the max. Shortest Common Supersequence: The shortest string that contains both A and B as subsequences. Length = len(A) + len(B) - LCS(A, B). Minimum Deletions to Make Strings Equal: Delete characters from both strings to make them identical. Answer = len(A) + len(B) - 2 * LCS(A, B).

When to Recognize It

Two strings (or sequences). You're comparing them character by character. You need the longest/shortest/minimum something between them. That's LCS family.

Pattern 3: Longest Increasing Subsequence (LIS)

The setup: Given a sequence, find the longest subsequence where elements are strictly increasing. State: dp[i] = length of the longest increasing subsequence ending at index i. Recurrence:

dp[i] = 1 + max(dp[j] for j in range(i) if arr[j] < arr[i])
# If no valid j exists, dp[i] = 1

O(n^2) Template

def lis(arr):
    n = len(arr)
    dp = [1] * n

for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

return max(dp)

O(n log n) Optimization with Binary Search

The O(n^2) solution is fine for interviews, but the O(n log n) version using patience sorting is worth knowing:

import bisect

def lis_fast(arr):
    tails = []  # tails[i] = smallest tail of all increasing subsequences of length i+1

for num in arr:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

return len(tails)

tails is always sorted, so binary search works. The key insight: tails[i] stores the smallest possible tail element for any increasing subsequence of length i+1. When a new element comes in, it either extends the longest subsequence (append) or replaces an element to keep tails as small as possible (enabling longer subsequences later).

Classic Problems

Russian Doll Envelopes: Given envelopes with (width, height), find the maximum number you can nest. Sort by width ascending, then by height descending within same width. Run LIS on the heights. The descending sort for same width prevents using two envelopes with the same width. Maximum Number of Events That Can Be Attended: Various scheduling problems reduce to LIS or LIS-like DP. Number of Longest Increasing Subsequences: Track both the length and the count. If you find an equal-length subsequence, add the count instead of replacing it. Longest Bitonic Subsequence: Compute LIS from left and LIS from right (longest decreasing subsequence). For each index, the bitonic subsequence length through that index is LIS_left[i] + LIS_right[i] - 1.

When to Recognize It

Single sequence. You want the longest subsequence with some ordering property (increasing, decreasing, bitonic). Elements don't need to be contiguous. That's LIS.

Pattern 4: Unbounded Knapsack / Coin Change

The setup: Like 0/1 knapsack, but each item can be used unlimited times. The classic formulation: given coin denominations, find the minimum number of coins to make a target amount. State: dp[amount] = minimum coins needed to make this amount. Recurrence:

dp[amount] = 1 + min(dp[amount - coin] for coin in coins if coin <= amount)

Base case: dp[0] = 0 (zero coins to make amount 0).

Template: Minimum Coins

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] != float('inf'):
                dp[a] = min(dp[a], dp[a - coin] + 1)

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

Template: Count Ways

"How many ways can you make amount X using these coins?" Same structure, but sum instead of min:

def coin_change_ways(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

for coin in coins:          # iterate coins in outer loop
        for a in range(coin, amount + 1):  # iterate amounts in inner loop
            dp[a] += dp[a - coin]

return dp[amount]

The loop order matters here. Coins in the outer loop ensures each combination is counted once (not each permutation). If you swap the loops, you count permutations instead.

Classic Problems

Climbing Stairs: You can climb 1 or 2 steps at a time. How many ways to reach step n? This is coin change (count ways) with coins = [1, 2]. It's also the Fibonacci sequence.

def climb_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = 1

for i in range(1, n + 1):
        dp[i] = dp[i-1]  # take 1 step
        if i >= 2:
            dp[i] += dp[i-2]  # take 2 steps

return dp[n]

Unbounded Knapsack: Same as 0/1 knapsack, but items can be reused. The only change: iterate capacity forward instead of backward.

def unbounded_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)

for i in range(len(weights)):
        for w in range(weights[i], capacity + 1):  # forward iteration
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

return dp[capacity]

Rod Cutting: Given a rod of length n and prices for each length 1..n, find the maximum revenue from cutting the rod into pieces. Direct unbounded knapsack. Perfect Squares: Find the minimum number of perfect squares that sum to n. Coin change with coins = [1, 4, 9, 16, ...]. Word Break: Given a string and a dictionary, can the string be segmented into dictionary words? Each word is a "coin" that can be reused.

def word_break(s, word_dict):
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    word_set = set(word_dict)

for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

return dp[n]

When to Recognize It

You have a target (amount, length, sum) and a set of choices you can use unlimited times. You want the minimum/maximum or count of ways. That's unbounded knapsack.

Pattern 5: Matrix Chain / Interval DP

The setup: You have a sequence, and you need to find the optimal way to split it into parts. The cost depends on where you split. State: dp[i][j] = optimal answer for the subproblem on the range [i, j]. Recurrence: Try every possible split point k between i and j:

dp[i][j] = optimize over k in [i, j-1]:
    dp[i][k] + dp[k+1][j] + cost(i, k, j)

Base case: dp[i][i] = 0 or a trivial value (single element, no split needed).

Template

def interval_dp(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]

# fill by increasing length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, k, j))

return dp[0][n-1]

The key insight: you iterate by increasing subproblem size (length 2, then 3, then 4, ...) so that when you compute dp[i][j], all smaller subproblems are already solved.

Classic Problems

Matrix Chain Multiplication: Given matrices A1 A2 ... * An, find the parenthesization that minimizes the number of scalar multiplications.

def matrix_chain(dims):
    # dims[i] = rows of matrix i, dims[i+1] = cols of matrix i
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]

for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]  dims[k+1]  dims[j+1]
                dp[i][j] = min(dp[i][j], cost)

return dp[0][n-1]

Burst Balloons: Given balloons with values, burst them one at a time to maximize the total coins. When you burst balloon i, you get nums[left] nums[i] nums[right]. The trick: think about which balloon to burst last in each range, not first. Minimum Cost to Merge Stones: Merge consecutive piles of stones, cost = sum of merged pile. Find the minimum total cost. Palindrome Partitioning II: Minimum cuts to partition a string into palindromes. Can be solved with interval DP (though there's also a more efficient 1D DP approach). Longest Palindromic Subsequence: dp[i][j] = length of longest palindromic subsequence in s[i..j].

def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

for i in range(n):
        dp[i][i] = 1

for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])

return dp[0][n-1]

When to Recognize It

You need to find the optimal way to split or merge a sequence. The cost depends on how you partition it. You're trying all possible split points. That's interval DP.

Common Mistakes Across All DP Patterns

Not identifying the state correctly. The state must capture all information needed to solve the subproblem. If your recurrence needs information that's not in your state, you're missing a dimension. Wrong base cases. Off-by-one errors in base cases cause the entire DP table to be wrong. Always verify your base case by thinking about the smallest possible input. Wrong iteration order. Bottom-up DP requires that when you compute dp[i][j], all subproblems it depends on are already computed. Draw the dependency arrows if you're unsure. Not considering space optimization. In interviews, mention that the 2D table can often be reduced to 1D. Even if you don't implement it, it shows awareness. Confusing 0/1 and unbounded knapsack. The only difference in the 1D optimization is the iteration direction for the capacity. Forward = unbounded (items reusable). Backward = 0/1 (items used once). This is subtle and easy to mix up.

Practice Problems by Pattern

0/1 Knapsack: Subset Sum, Partition Equal Subset Sum, Target Sum, Last Stone Weight II LCS: Edit Distance, Longest Common Substring, Delete Operation for Two Strings, Shortest Common Supersequence LIS: Longest Increasing Subsequence, Russian Doll Envelopes, Number of LIS, Maximum Length of Pair Chain Unbounded Knapsack: Coin Change (min), Coin Change II (count), Climbing Stairs, Perfect Squares, Word Break Interval DP: Burst Balloons, Matrix Chain Multiplication, Minimum Cost to Merge Stones, Longest Palindromic Subsequence, Palindrome Partitioning II

Work through these patterns systematically on CodeUp. Once you can recognize which pattern a problem belongs to, the hard part is over — the template handles the rest.