Dynamic Programming Patterns Cheat Sheet: Recognize Any DP Problem in 30 Seconds

Here's the thing about dynamic programming: it's not about being smart enough to derive a recurrence from scratch. It's about recognizing which of roughly 7 patterns a problem belongs to. Once you identify the pattern, the solution structure is basically the same every time.

I've seen people spend months on DP and still freeze in interviews because they treated every problem as unique. Don't do that. Learn the patterns, learn the recognition signals, and the problems will start solving themselves.

The 7 DP Patterns

Pattern 1: 0/1 Knapsack

Recognition signal: "Choose or skip each item." You have a collection of items and for each one, you either include it or exclude it. There's usually a constraint (weight, capacity, target sum). Classic problems: Subset Sum, Partition Equal Subset Sum, Target Sum, 0/1 Knapsack.

# 0/1 Knapsack — 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 item i
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1])  # take item i

return dp[n][capacity]

The key: dp[i-1] — you look at the previous row because each item can only be used once. That's what makes it "0/1."

# Partition Equal Subset Sum — "can we split into two equal halves?"
def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

for num in nums:
        for t in range(target, num - 1, -1):  # reverse to avoid reusing
            dp[t] = dp[t] or dp[t - num]

return dp[target]

Notice the reverse iteration — that's the space-optimized trick for 0/1 knapsack. Going right-to-left ensures each item is only considered once.

Pattern 2: Unbounded Knapsack

Recognition signal: "Unlimited supply of items." Same as 0/1 knapsack but you can reuse items. Classic problems: Coin Change, Coin Change II, Rod Cutting, Unbounded Knapsack.

# Coin Change — minimum coins to reach amount
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

The difference from 0/1: we iterate forward (not reverse), which allows reusing the same coin multiple times. That single direction change is the entire difference between the two patterns.

Pattern 3: Fibonacci-like (Linear DP)

Recognition signal: "Current state depends on previous 1-2 states." The recurrence looks like dp[i] = f(dp[i-1], dp[i-2]). Classic problems: Climbing Stairs, House Robber, Decode Ways, Maximum Subarray.

# House Robber — can't rob adjacent houses
def rob(nums):
    if len(nums) <= 2:
        return max(nums) if nums else 0

prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr

return prev1

At each house: either skip it (take prev1) or rob it (take prev2 + nums[i]). Only two previous values needed, so O(1) space.

# Decode Ways — how many ways to decode a digit string
def num_decodings(s):
    if not s or s[0] == '0':
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

for i in range(2, n + 1):
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i - 2]

return dp[n]

Pattern 4: Longest Common Subsequence (LCS)

Recognition signal: "Two strings or arrays, match/compare characters." Usually involves a 2D table where dp[i][j] represents some property of s1[:i] and s2[:j]. Classic problems: Longest Common Subsequence, Edit Distance, Distinct Subsequences, Shortest Common Supersequence.

# Longest Common Subsequence
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]

# Edit Distance — minimum operations to transform word1 into word2
def min_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]

The pattern: characters match? Diagonal. Don't match? Take the best of three operations.

Pattern 5: Palindrome

Recognition signal: "Palindromic substring or subsequence." Usually involves expanding from the center or a 2D DP on substrings. Classic problems: Longest Palindromic Substring, Longest Palindromic Subsequence, Palindrome Partitioning.

# Longest Palindromic Substring — expand from center
def longest_palindrome(s):
    result = ""

def expand(left, right):
        nonlocal result
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > len(result):
                result = s[left:right + 1]
            left -= 1
            right += 1

for i in range(len(s)):
        expand(i, i)      # odd-length palindromes
        expand(i, i + 1)  # even-length palindromes

return result

Expand-from-center is O(n^2) time, O(1) space. Simpler than the DP approach and usually what interviewers prefer.

Pattern 6: Grid DP

Recognition signal: "Movement on a 2D grid, usually right and down." dp[i][j] depends on dp[i-1][j] and dp[i][j-1]. Classic problems: Unique Paths, Minimum Path Sum, Dungeon Game, Maximal Square.

# Unique Paths — how many ways from top-left to bottom-right
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]

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

return dp[m - 1][n - 1]

# Minimum Path Sum
def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            elif i == 0:
                grid[i][j] += grid[i][j - 1]
            elif j == 0:
                grid[i][j] += grid[i - 1][j]
            else:
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
    return grid[m - 1][n - 1]

Pattern 7: Interval DP

Recognition signal: "Merge or split ranges, cost of combining subarrays." Usually dp[i][j] represents the answer for the subarray from index i to j. Classic problems: Burst Balloons, Matrix Chain Multiplication, Minimum Cost Tree From Leaf Values.

# Burst Balloons — maximize coins from bursting balloons
def max_coins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

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

return dp[0][n - 1]

The trick: think about which balloon you burst last in a range, not first. This gives you independent subproblems on the left and right.

Quick Reference Table

Problem	Pattern	Difficulty
Climbing Stairs	Fibonacci-like	Easy
House Robber	Fibonacci-like	Medium
Decode Ways	Fibonacci-like	Medium
Subset Sum	0/1 Knapsack	Medium
Partition Equal Subset	0/1 Knapsack	Medium
Target Sum	0/1 Knapsack	Medium
Coin Change	Unbounded Knapsack	Medium
Coin Change II	Unbounded Knapsack	Medium
Rod Cutting	Unbounded Knapsack	Medium
LCS	LCS	Medium
Edit Distance	LCS	Medium
Longest Palindromic Substring	Palindrome	Medium
Palindrome Partitioning	Palindrome	Medium
Unique Paths	Grid	Medium
Minimum Path Sum	Grid	Medium
Maximal Square	Grid	Medium
Burst Balloons	Interval	Hard
Matrix Chain Multiply	Interval	Hard

The 30-Second Recognition Test

When you see a new DP problem, ask these questions in order:

1. Choose/skip items with a constraint? -> 0/1 Knapsack
2. Unlimited item usage? -> Unbounded Knapsack
3. Depends on previous 1-2 states? -> Fibonacci-like
4. Two strings, comparing characters? -> LCS
5. Palindrome in a string? -> Palindrome
6. Movement on a 2D grid? -> Grid
7. Merge/split ranges for optimal cost? -> Interval

That's it. Seven questions, seven patterns. Every DP problem in a coding interview falls into one of these buckets.

If you want to drill these patterns with guided hints instead of just staring at problems, CodeUp organizes DP problems by pattern and walks you through the recognition process step by step — which builds the intuition way faster than grinding random LeetCode problems.