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

Originally published on LeetCopilot Blog

---

DP doesn't have to be scary. Master these 7 patterns and you'll be able to solve most dynamic programming problems you encounter in interviews.

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

Pattern	Example Problems
1. Fibonacci	Climbing Stairs, House Robber
2. 0/1 Knapsack	Subset Sum, Partition Equal Subset
3. Unbounded Knapsack	Coin Change, Rod Cutting
4. Longest Common Subsequence	LCS, Edit Distance
5. Longest Increasing Subsequence	LIS, Russian Doll Envelopes
6. Grid/Matrix DP	Unique Paths, Min Path Sum
7. Interval DP	Matrix Chain Multiplication

---

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:

Problem	Recurrence
Climbing Stairs	dp[i] = dp[i-1] + dp[i-2]
House Robber	dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Decode Ways	dp[i] = dp[i-1] + dp[i-2] (with conditions)

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:

Problem	Twist
0/1 Knapsack	Classic max value with weight limit
Subset Sum	Can we make target sum? (boolean)
Partition Equal Subset	Can we split into two equal halves?
Target Sum	Assign +/- to reach target

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:

Problem	Goal
Coin Change	Min coins to make amount
Coin Change II	Number of ways to make amount
Rod Cutting	Max revenue from cutting

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:

Problem	Variation
Longest Common Subsequence	Classic LCS
Edit Distance	Insert, delete, replace costs
Longest Palindromic Subsequence	LCS(s, reverse(s))

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:

Problem	Twist
Longest Increasing Subsequence	Classic LIS
Number of LIS	Count all LIS
Russian Doll Envelopes	2D LIS

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:

Problem	Goal
Unique Paths	Count paths to reach end
Unique Paths II	With obstacles
Min Path Sum	Minimum cost path
Maximal Square	Largest square of 1s

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:

Problem	Description
Matrix Chain Multiplication	Optimal parenthesization
Burst Balloons	Max coins from bursting
Palindrome Partitioning	Min cuts for palindromes

---

Pattern Recognition Cheat Sheet

If the problem asks...	Try this pattern
Min/max ways to reach end	Fibonacci / Grid DP
Include/exclude items once	0/1 Knapsack
Include items multiple times	Unbounded Knapsack
Compare two strings	LCS
Find increasing sequence	LIS
Navigate a grid	Grid DP
Optimize over ranges	Interval DP

---

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!

---

If you're looking for an AI assistant to help you master LeetCode patterns and prepare for coding interviews, check out LeetCopilot.