Dynamic Programming Patterns 2026: 8 Core Patterns [20+ Problems Solved]

Last Updated: June 2026

The Pattern-First Approach to DP

Candidates report that DP is the single pattern that most frequently separates shortlisted candidates from rejected ones in FAANG rounds. Based on public preparation resources and candidate-reported interview accounts, roughly 30% of Google and Amazon coding questions involve DP. Most candidates fail DP questions because they try to invent a recurrence from scratch for each problem. The correct approach is pattern recognition: identify which of the 8 core patterns fits, apply the corresponding template, then modify for the specific problem constraints.

This guide teaches the 8 patterns with 2-3 solved problems per pattern so you internalize the template, not just the solution.

The DP Framework (Apply to Every Problem)

STEP 1: Define state   - what does dp[i] or dp[i][j] represent?
STEP 2: Write recurrence - dp[i] = f(dp[i-1], dp[i-2], ...)
STEP 3: Set base cases - dp[0], dp[1], etc.
STEP 4: Determine order - which direction to fill the table?
STEP 5: Extract answer  - where is the final answer in the table?

Pattern 1: Linear DP (Fibonacci Style)

Signature: Single sequence. Decision at each index depends only on a few previous indices.

Template:

dp[0] = base0
dp[1] = base1
for i in range(2, n + 1):
    dp[i] = f(dp[i-1], dp[i-2])

Problem 1.1: Climbing Stairs

def climb_stairs(n):
    """
    dp[i] = ways to reach step i
    dp[i] = dp[i-1] + dp[i-2]  (take 1 or 2 steps)
    Time: O(n)  Space: O(1) space-optimized
    """
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

print(climb_stairs(5))  # 8

Problem 1.2: House Robber

def rob(nums):
    """
    dp[i] = max money robbing houses [0..i]
    dp[i] = max(dp[i-1], dp[i-2] + nums[i])  (skip or rob)
    Time: O(n)  Space: O(1)
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

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

Problem 1.3: Jump Game II (Minimum Jumps)

def jump(nums):
    """
    Greedy DP: track farthest reachable at each step.
    Time: O(n)  Space: O(1)
    """
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

print(jump([2, 3, 1, 1, 4]))  # 2

Pattern 2: 0/1 Knapsack

Signature: Items with weight and value. Each item used at most once. Maximize value within weight budget.

State: dp[i][w] = max value using first i items with weight limit w

Recurrence:

• Skip item i: dp[i][w] = dp[i-1][w]
• Take item i: dp[i][w] = dp[i-1][w-wt[i]] + val[i] (if w >= wt[i])
• dp[i][w] = max(skip, take)

def knapsack_01(weights, values, W):
    """
    Time: O(n*W)  Space: O(W) space-optimized (1D rolling array)
    """
    n = len(weights)
    dp = [0] * (W + 1)

    for i in range(n):
        # Iterate RIGHT TO LEFT to avoid using item i twice
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

Problem 2.1: Subset Sum

def can_partition_subset(nums, target):
    """
    0/1 knapsack where value = weight = num.
    Can we achieve exactly `target` sum?
    Time: O(n*target)  Space: O(target)
    """
    dp = [False] * (target + 1)
    dp[0] = True

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

    return dp[target]

print(can_partition_subset([1, 5, 11, 5], 11))  # True

Problem 2.2: Partition Equal Subset Sum

def can_partition(nums):
    """
    Split into two equal-sum subsets = subset sum to total/2.
    Time: O(n * sum)  Space: O(sum)
    """
    total = sum(nums)
    if total % 2 != 0:
        return False
    return can_partition_subset(nums, total // 2)

print(can_partition([1, 5, 11, 5]))  # True
print(can_partition([1, 2, 3, 5]))   # False

Problem 2.3: Target Sum (Count Ways)

def find_target_sum_ways(nums, target):
    """
    Assign + or - to each number. Count ways to reach target.
    Equivalent to: find subset S where sum(S) = (total + target) / 2
    Time: O(n * sum)  Space: O(sum)
    """
    total = sum(nums)
    if (total + target) % 2 != 0 or abs(target) > total:
        return 0

    s = (total + target) // 2
    dp = [0] * (s + 1)
    dp[0] = 1

    for num in nums:
        for j in range(s, num - 1, -1):
            dp[j] += dp[j - num]

    return dp[s]

print(find_target_sum_ways([1, 1, 1, 1, 1], 3))  # 5

Pattern 3: Unbounded Knapsack

Signature: Same as 0/1 but each item can be used unlimited times.

Key difference from 0/1: Iterate FORWARD (left to right) in inner loop.

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

    for w in range(1, W + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

Problem 3.1: Coin Change (Min Coins)

def coin_change(coins, amount):
    """
    Unbounded knapsack: minimize coins to reach amount.
    Time: O(n * amount)  Space: O(amount)
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for a in range(coin, amount + 1):  # forward iteration
            dp[a] = min(dp[a], dp[a - coin] + 1)

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

print(coin_change([1, 5, 6, 9], 11))  # 2 (5+6)

Problem 3.2: Coin Change II (Count Ways)

def change(amount, coins):
    """
    Count distinct ways to make amount using unlimited coins.
    Time: O(n * amount)  Space: O(amount)
    """
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]

    return dp[amount]

print(change(5, [1, 2, 5]))  # 4 ways

Pattern 4: LCS / Edit Distance

Signature: Two sequences being compared. 2D DP table.

State: dp[i][j] = answer for prefix of length i from seq1 and j from seq2

Problem 4.1: Longest Common Subsequence

def lcs(text1, text2):
    """
    dp[i][j] = LCS of text1[:i] and text2[:j]
    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])
    Time: O(m*n)  Space: O(m*n) or O(min(m,n)) optimized
    """
    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", "abc"))     # 3

Problem 4.2: Edit Distance

def min_distance(word1, word2):
    """
    dp[i][j] = min edits to convert word1[:i] to word2[:j]
    If chars match: dp[i][j] = dp[i-1][j-1]
    Else: dp[i][j] = 1 + min(insert, delete, replace)
    Time: O(m*n)  Space: O(m*n)
    """
    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][j - 1],      # insert
                    dp[i - 1][j],      # delete
                    dp[i - 1][j - 1]   # replace
                )

    return dp[m][n]

print(min_distance("horse", "ros"))    # 3
print(min_distance("intention", "execution"))  # 5

Pattern 5: Palindrome DP

Signature: Single sequence, reasoning about palindromic properties.

Problem 5.1: Longest Palindromic Subsequence

def longest_palindromic_subsequence(s):
    """
    LPS(s) = LCS(s, reversed(s))
    Time: O(n^2)  Space: O(n^2)
    """
    return lcs(s, s[::-1])

print(longest_palindromic_subsequence("bbbab"))   # 4 ("bbbb")

Problem 5.2: Minimum Cuts for Palindrome Partitioning

def min_cut(s):
    """
    dp[i] = min cuts for s[0..i] to be all palindromes.
    Time: O(n^2)  Space: O(n^2)
    """
    n = len(s)

    # Precompute is_palindrome[i][j]
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n - 1):
        is_pal[i][i + 1] = (s[i] == s[i + 1])
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j] and is_pal[i + 1][j - 1])

    dp = list(range(n))  # worst case: n-1 cuts
    for i in range(1, n):
        if is_pal[0][i]:
            dp[i] = 0
        else:
            for j in range(1, i + 1):
                if is_pal[j][i]:
                    dp[i] = min(dp[i], dp[j - 1] + 1)

    return dp[n - 1]

print(min_cut("aab"))   # 1 ("aa" | "b")

Pattern 6: Interval DP

Signature: Problem on a range [i, j]. Optimal answer for [i, j] depends on splitting at k.

Template:

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = min/max over k in (i, j)

Problem 6.1: Matrix Chain Multiplication

def matrix_chain_order(dims):
    """
    dims[i-1] x dims[i] = dimensions of matrix i.
    Find minimum scalar multiplications.
    Time: O(n^3)  Space: O(n^2)
    """
    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]

print(matrix_chain_order([40, 20, 30, 10, 30]))  # 26000

Problem 6.2: Burst Balloons

def max_coins(nums):
    """
    Trick: add boundary 1s. dp[i][j] = max coins from bursting all in (i,j) exclusive.
    Time: O(n^3)  Space: O(n^2)
    """
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left + 1, right):
                coins = nums[left] * nums[k] * nums[right]
                dp[left][right] = max(dp[left][right],
                                      dp[left][k] + dp[k][right] + coins)

    return dp[0][n - 1]

print(max_coins([3, 1, 5, 8]))  # 167

Pattern 7: Tree DP

Signature: DP on a rooted tree. State defined per subtree. Parent state depends on children states.

Problem 7.1: Diameter of Binary Tree

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameter_of_binary_tree(root):
    """
    At each node: diameter through this node = left_depth + right_depth.
    dp (height) computed bottom-up.
    Time: O(n)  Space: O(h)
    """
    max_diameter = [0]

    def height(node):
        if not node:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        max_diameter[0] = max(max_diameter[0], lh + rh)
        return 1 + max(lh, rh)

    height(root)
    return max_diameter[0]

Problem 7.2: House Robber III (Rob Tree)

def rob_tree(root):
    """
    At each node: rob this node (skip children) or skip (take best of children).
    Return pair: (max without robbing root, max with robbing root)
    Time: O(n)  Space: O(h)
    """
    def dp(node):
        if not node:
            return (0, 0)

        left_skip, left_rob = dp(node.left)
        right_skip, right_rob = dp(node.right)

        # Rob this node: can't rob children
        with_root = node.val + left_skip + right_skip
        # Skip this node: take best from each child
        without_root = max(left_skip, left_rob) + max(right_skip, right_rob)

        return (without_root, with_root)

    skip, rob = dp(root)
    return max(skip, rob)

Pattern 8: Bitmask DP

Signature: Problem over all subsets of n elements. State: bitmask representing which elements have been used.

When to use: n <= 20, problems asking about optimal ordering or visiting all nodes.

Problem 8.1: Traveling Salesman Problem (TSP)

def tsp(dist):
    """
    dp[mask][i] = min cost to visit all cities in mask, ending at city i.
    Time: O(2^n * n^2)  Space: O(2^n * n)
    """
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # Start at city 0, mask = 0001

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask >> u & 1):
                continue

            for v in range(n):
                if mask >> v & 1:
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])

    full_mask = (1 << n) - 1
    return min(dp[full_mask][i] + dist[i][0] for i in range(1, n))

Problem 8.2: Minimum XOR Sum (Assignment Problem)

def minimum_xor_sum(nums1, nums2):
    """
    Assign each nums2[j] to a nums1[i] (bijection). Minimize sum of XOR pairs.
    dp[mask] = min XOR sum assigning nums2[j] for j in mask to first popcount(mask) elements.
    Time: O(2^n * n)  Space: O(2^n)
    """
    n = len(nums1)
    dp = [float('inf')] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        i = bin(mask).count('1')  # which nums1 index we are assigning to
        if i >= n:
            continue
        for j in range(n):
            if not (mask >> j & 1):
                dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + (nums1[i] ^ nums2[j]))

    return dp[(1 << n) - 1]

Pattern Recognition Guide

Complexity Summary

Related Articles

• Dynamic Programming Questions Placement
• Binary Search Patterns 2026
• Graph Traversal Patterns 2026
• Must-Do Coding Questions
• System Design Interview Questions 2026