Common DP Patterns

Most interview DP problems fall into a few recognizable patterns. Master these and you'll handle 80% of DP questions.

Pattern 1: Linear Sequence (1D DP)

Recognition: Process elements one by one, decision at each element.

Template:

dp = [0] * n
dp[0] = base_case

for i in range(1, n):
    dp[i] = function_of(dp[i-1], dp[i-2], ..., nums[i])

return dp[n-1]

Example - House Robber:

def rob(nums):
    """Can't rob adjacent houses, maximize money"""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

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

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

    return prev1

Pattern 2: Grid Paths (2D DP)

Recognition: Navigate a grid, find paths/costs.

Template:

dp = [[0] * cols for _ in range(rows)]
# Initialize first row/column
dp[0][0] = grid[0][0]

for i in range(rows):
    for j in range(cols):
        if i == 0 and j == 0:
            continue
        dp[i][j] = function_of(dp[i-1][j], dp[i][j-1], grid[i][j])

return dp[rows-1][cols-1]

Example - Unique Paths:

def uniquePaths(m, n):
    """Count paths from top-left to bottom-right"""
    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]

Pattern 3: Knapsack (Items + Capacity)

Recognition: Items with weight/value, limited capacity, maximize value.

0/1 Knapsack Template:

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]

Example - Coin Change:

def coinChange(coins, amount):
    """Minimum coins to make 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

Pattern 4: Palindromes (Substring DP)

Recognition: Substrings, palindromes, matching.

Template:

n = len(s)
dp = [[False] * n for _ in range(n)]

# Base case: single characters
for i in range(n):
    dp[i][i] = True

# Check all substring lengths
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1

        if s[i] == s[j]:
            if length == 2:
                dp[i][j] = True
            else:
                dp[i][j] = dp[i+1][j-1]

Example - Longest Palindromic Substring:

def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s

    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1

    # Single characters
    for i in range(n):
        dp[i][i] = True

    # Two characters
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start, max_len = i, 2

    # Longer substrings
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start, max_len = i, length

    return s[start:start + max_len]

Pattern 5: Subsequences (LCS variants)

Recognition: Longest common/increasing subsequence.

Template:

dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

for i in range(1, len(s1) + 1):
    for j in range(1, len(s2) + 1):
        if s1[i-1] == s2[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[len(s1)][len(s2)]

Example - Longest Common Subsequence:

def longestCommonSubsequence(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]

Pattern 6: Partition Problems

Recognition: Split array into groups, maximize/minimize something.

Example - Partition Equal Subset Sum:

def canPartition(nums):
    """Can we partition into two equal sum subsets?"""
    total = sum(nums)
    if total % 2 != 0:
        return False

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

    for num in nums:
        # Traverse backwards to avoid using same element twice
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]

Pattern 7: State Machine DP

Recognition: Multiple states, transitions between states.

Example - Best Time to Buy/Sell Stock with Cooldown:

def maxProfit(prices):
    if not prices:
        return 0

    # States: hold stock, sold (cooldown), no stock
    hold = -prices[0]
    sold = 0
    rest = 0

    for price in prices[1:]:
        prev_hold = hold
        prev_sold = sold
        prev_rest = rest

        hold = max(prev_hold, prev_rest - price)
        sold = prev_hold + price
        rest = max(prev_rest, prev_sold)

    return max(sold, rest)

Quick Reference Table

Choosing the Right Pattern

Decision Tree:

Is it about sequences/arrays?
├─ Yes: Single array?
│  ├─ Yes: Linear 1D (dp[i])
│  └─ No: Two sequences? → Subsequence pattern (dp[i][j])
│
└─ No: Grid?
   ├─ Yes: Grid path pattern (dp[i][j])
   └─ No: Items and capacity?
      ├─ Yes: Knapsack pattern
      └─ No: Multiple states? → State machine

Key Takeaway

Most DP problems are variations of these 7 patterns. Learn to recognize the pattern, apply the template, and adapt to the specific problem. The pattern tells you the DP table structure; the problem tells you the recurrence relation.