Dynamic Programming: 7 Patterns That Solve 90% of DP Problems

Dynamic programming is the most feared topic in coding interviews. But here's the secret: most DP problems fall into just 7 patterns.

Learn these patterns, and you'll go from "I have no idea where to start" to "Oh, this is just a variation of pattern X."

TL;DR: The 7 DP Patterns

How to Approach Any DP Problem

Before diving into patterns, here's a framework:

Step 1: Identify if it's DP

• Can the problem be broken into smaller subproblems?
• Are there overlapping subproblems?
• Does it ask for optimal (min/max) or count of ways?

Step 2: Define the state

• What information do you need to track?
• What are the parameters that change?

Step 3: Write the recurrence

• How do you transition from smaller states to larger ones?

Step 4: Decide on top-down or bottom-up

• Top-down (memoization): Easier to write
• Bottom-up (tabulation): Usually faster

Pattern 1: Fibonacci (Linear DP)

Characteristic: Each state depends on the previous 1-2 states.

Template:

dp[i] = dp[i-1] + dp[i-2]  # or some combination

Key Problems:

Example: House Robber

def rob(nums):
    if len(nums) <= 2:
        return max(nums) if nums else 0
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

Pattern 2: 0/1 Knapsack

Characteristic: Choose to include or exclude each item exactly once.

Template:

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

Key Problems:

Example: Subset Sum

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

Pattern 3: Unbounded Knapsack

Characteristic: Can use each item unlimited times.

Template:

dp[w] = min(dp[w], dp[w-coin] + 1)  # for Coin Change

Key Problems:

Example: Coin Change

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Pattern 4: Longest Common Subsequence (LCS)

Characteristic: Two strings, matching/comparing characters.

Template:

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

Key Problems:

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 5: Longest Increasing Subsequence (LIS)

Characteristic: Find increasing elements (not necessarily contiguous).

Template:

dp[i] = max(dp[j] + 1 for all j < i if nums[j] < nums[i])

Key Problems:

Example: LIS (O(n²) version)

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Pattern 6: Grid/Matrix DP

Characteristic: Navigate a 2D grid, usually from top-left to bottom-right.

Template:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

Key Problems:

Example: Unique Paths

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

Pattern 7: Interval DP

Characteristic: Problems involving intervals or ranges.

Template:

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

Key Problems:

Pattern Recognition Cheat Sheet

Practice Problems by Pattern

Start Here (Easy):

1. Climbing Stairs (Fibonacci)
2. House Robber (Fibonacci)
3. Coin Change (Unbounded Knapsack)
4. Unique Paths (Grid DP)

Intermediate:

1. Longest Common Subsequence (LCS)
2. Longest Increasing Subsequence (LIS)
3. Word Break (Unbounded Knapsack variant)
4. Partition Equal Subset Sum (0/1 Knapsack)

Advanced:

1. Edit Distance (LCS)
2. Burst Balloons (Interval DP)
3. Russian Doll Envelopes (LIS)
4. Interleaving String (LCS variant)

Tips for DP Success

1. Start with recursion

Write the brute-force recursive solution first, then add memoization.

2. Identify the state

What changes between subproblems? That's your state.

3. Draw the recurrence

Visualize how states connect before coding.

4. Practice pattern recognition

When stuck, use LeetCopilot for hints on which pattern applies.

5. Don't memorize, understand

Understanding why a pattern works is more valuable than memorizing code.

FAQ

How many DP problems should I solve?
20-30 well-understood problems covering all patterns is better than 100 random ones.

Should I learn top-down or bottom-up first?
Top-down (memoization) is usually easier to start with.

Why is DP so hard?
It's hard because it's not intuitive at first. With pattern practice, it becomes mechanical.

Conclusion

DP is learnable. Master these 7 patterns:

1. Fibonacci — Linear dependencies
2. 0/1 Knapsack — Include/exclude once
3. Unbounded Knapsack — Include multiple times
4. LCS — String comparisons
5. LIS — Increasing sequences
6. Grid DP — 2D traversal
7. Interval DP — Range optimization

Practice 3-5 problems per pattern, and DP will become your strength instead of your weakness.

Use LeetCopilot when stuck—get hints without spoiling the learning.

Good luck!