Why are DP patterns important?

Knowing patterns helps solve new problems quickly. Most DP problems are variations of a few patterns.

Difference between LCS and LIS?

LCS is the common subsequence of two sequences, LIS is the increasing subsequence of one sequence.

Why is the knapsack problem important?

It is the basic pattern for resource allocation and optimization problems. Many problems are knapsack variations.

DP Patterns | Dynamic Programming Problem-Solving Strategies

2024년 9월 16일 · 22분 읽기 · 수정 2026년 3월 28일 Advanced Tutorial

이 글의 핵심

Master DP patterns: problem-solving strategies for dynamic programming. Learn 1D DP, 2D DP, knapsack, LCS, and LIS patterns with principles and code examples.

Introduction

”DP Problems Are Patterns”

Most DP problems are variations of a few patterns. Master the patterns and new problems become easy.

1. 1D DP Patterns

In 1D DP, dp[i] typically means “optimal value from first to ith element” or “optimal value for subproblem of size i”. The two examples below are representative patterns that fill the next cell using only previous cells.

Pattern 1: Using Previous Values

def climb_stairs(n):
    """
    Climbing stairs (1 or 2 steps)
    dp[i] = dp[i-1] + dp[i-2]
    """
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]
print(climb_stairs(5))  # 8

Pattern 2: Max/Min Selection

def rob(houses):
    """
    House Robber (cannot rob adjacent houses)
    dp[i] = max(dp[i-1], dp[i-2] + houses[i])
    """
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
    
    dp = [0] * len(houses)
    dp[0] = houses[0]
    dp[1] = max(houses[0], houses[1])
    
    for i in range(2, len(houses)):
        dp[i] = max(dp[i-1], dp[i-2] + houses[i])
    
    return dp[-1]
# Test
print(rob([2, 7, 9, 3, 1]))  # 12 (2+9+1)

2. 2D DP Patterns

Pattern 1: Grid Paths

def unique_paths(m, n):
    """
    Number of paths in m×n grid
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
    """
    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]
print(unique_paths(3, 7))  # 28

Pattern 2: LCS (Longest Common Subsequence)

def lcs(s1, s2):
    """
    Longest Common Subsequence
    "ABCDGH", "AEDFHR" → "ADH" (length 3)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]
# Test
print(lcs("ABCDGH", "AEDFHR"))  # 3

LCS Backtracking:

def lcs_with_string(s1, s2):
    """
    Return LCS string, not just length
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Build DP table
    for i in range(1, m + 1):
        for j in range(1, n + 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])
    
    # Backtrack to find string
    result = []
    i, j = m, n
    
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return '.join(reversed(result))
# Test
print(lcs_with_string("ABCDGH", "AEDFHR"))  # "ADH"

3. Knapsack Problem Patterns

0-1 Knapsack

def knapsack_01(weights, values, capacity):
    """
    Each item 0 or 1 time
    """
    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):
            # Don't take
            dp[i][w] = dp[i-1][w]
            
            # Take
            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]
# Test
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_01(weights, values, capacity))  # 10

Space Optimized (1D):

def knapsack_01_optimized(weights, values, capacity):
    """
    O(capacity) space
    """
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # Iterate backwards to prevent overwriting
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

Unbounded Knapsack

def knapsack_unbounded(weights, values, capacity):
    """
    Each item unlimited times
    """
    dp = [0] * (capacity + 1)
    
    for w in range(capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]
# Test
weights = [1, 3, 4]
values = [15, 50, 60]
capacity = 8
print(knapsack_unbounded(weights, values, capacity))  # 120

4. LIS (Longest Increasing Subsequence)

O(n²) Solution

def lis_n2(arr):
    """
    Longest Increasing Subsequence
    [10, 9, 2, 5, 3, 7, 101, 18] → 4 ([2,3,7,18])
    """
    n = len(arr)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)
# Test
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_n2(arr))  # 4

O(n log n) Solution

import bisect
def lis_nlogn(arr):
    """
    Using binary search
    """
    dp = []
    
    for num in arr:
        pos = bisect.bisect_left(dp, num)
        
        if pos == len(dp):
            dp.append(num)
        else:
            dp[pos] = num
    
    return len(dp)
# Test
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_nlogn(arr))  # 4

How O(n log n) Works:

arr = [10, 9, 2, 5, 3, 7, 101, 18]
Step 1: num=10, dp=[10]
Step 2: num=9,  dp=[9]     (replace 10)
Step 3: num=2,  dp=[2]     (replace 9)
Step 4: num=5,  dp=[2,5]   (append)
Step 5: num=3,  dp=[2,3]   (replace 5)
Step 6: num=7,  dp=[2,3,7] (append)
Step 7: num=101,dp=[2,3,7,101] (append)
Step 8: num=18, dp=[2,3,7,18]  (replace 101)
Length = 4

5. Edit Distance Pattern

def edit_distance(s1, s2):
    """
    Minimum operations to convert s1 to s2
    Operations: insert, delete, replace
    
    "horse", "ros" → 3
    (replace h→r, delete o, delete e)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initial values
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # Fill table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,    # delete
                    dp[i][j-1] + 1,    # insert
                    dp[i-1][j-1] + 1   # replace
                ) 
    
    return dp[m][n]
# Test
print(edit_distance("horse", "ros"))  # 3

6. Practical Tips

DP Pattern Recognition

# 1. 1D DP
# - Using previous values: dp[i] = f(dp[i-1], dp[i-2])
# - Examples: Fibonacci, climbing stairs
# 2. 2D DP
# - Grid: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# - String: dp[i][j] = f(s1[i], s2[j])
# - Examples: LCS, edit distance
# 3. Knapsack
# - Take/don't take: dp[i][w] = max(don't take, take)
# - Examples: 0-1 knapsack, coin change

Debugging Tips

# 1. Print DP table
def print_dp_table(dp):
    for row in dp:
        print(row)
# 2. Check initial values
# - Are dp[0], dp[1] correct?
# - Are boundary conditions handled?
# 3. Verify recurrence relation
# - Is the formula correct?
# - Are indices correct?

Common Mistakes

# ❌ Wrong: Forgot initial values
dp = [0] * n
# dp[0], dp[1] not set!
# ✅ Correct: Set initial values
dp = [0] * n
dp[0] = 1
dp[1] = 1
# ❌ Wrong: Index out of bounds
for i in range(n):
    dp[i] = dp[i-1] + dp[i-2]  # i=0, i=1 error!
# ✅ Correct: Start from valid index
for i in range(2, n):
    dp[i] = dp[i-1] + dp[i-2]

7. Advanced Patterns

Partition DP

def word_break(s, word_dict):
    """
    Check if string can be segmented into dictionary words
    s = "leetcode", wordDict = ["leet", "code"] → True
    """
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_dict:
                dp[i] = True
                break
    
    return dp[n]
# Test
s = "leetcode"
word_dict = {"leet", "code"}
print(word_break(s, word_dict))  # True

State Machine DP

def max_profit_cooldown(prices):
    """
    Stock trading with cooldown
    States: hold, sold, rest
    """
    if not prices:
        return 0
    
    n = len(prices)
    hold = [0] * n
    sold = [0] * n
    rest = [0] * n
    
    hold[0] = -prices[0]
    
    for i in range(1, n):
        hold[i] = max(hold[i-1], rest[i-1] - prices[i])
        sold[i] = hold[i-1] + prices[i]
        rest[i] = max(rest[i-1], sold[i-1])
    
    return max(sold[-1], rest[-1])
# Test
prices = [1, 2, 3, 0, 2]
print(max_profit_cooldown(prices))  # 3

Summary

Key Points

1D DP: Use previous values, max/min selection
2D DP: Grid, LCS, knapsack
LIS: O(n²) or O(n log n)
Pattern Recognition: Problem → Pattern matching

Pattern Checklist

Pattern	Recurrence	Example
1D Previous	`dp[i] = f(dp[i-1])`	Climbing stairs
1D Max/Min	`dp[i] = max(...)`	House robber
2D Grid	`dp[i][j] = f(dp[i-1][j], dp[i][j-1])`	Unique paths
2D String	`dp[i][j] = f(s1[i], s2[j])`	LCS, Edit distance
Knapsack	`dp[i][w] = max(take, don't take)`	0-1 Knapsack

Keywords

Dynamic Programming, DP, Patterns, Memoization, Tabulation, LCS, LIS, Knapsack, Edit Distance, Coding Interview, Algorithm, Problem Solving

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Master DP patterns: problem-solving strategies for dynamic programming. Learn 1D DP, 2D DP, knapsack, LCS, and LIS patte…

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

DP Patterns | Dynamic Programming Problem-Solving Strategies

이 글의 핵심

Introduction

”DP Problems Are Patterns”

Most DP problems are variations of a few patterns. Master the patterns and new problems become easy.

1. 1D DP Patterns

Pattern 1: Using Previous Values

Pattern 2: Max/Min Selection

2. 2D DP Patterns

Pattern 1: Grid Paths

Pattern 2: LCS (Longest Common Subsequence)

3. Knapsack Problem Patterns

0-1 Knapsack

Unbounded Knapsack

4. LIS (Longest Increasing Subsequence)

O(n²) Solution

O(n log n) Solution

5. Edit Distance Pattern

6. Practical Tips

DP Pattern Recognition

Debugging Tips

Common Mistakes

7. Advanced Patterns

Partition DP

State Machine DP

Summary

Key Points

Pattern Checklist

Recommended Problems

Baekjoon

LeetCode

Programmers

Keywords

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

Q. What should I read before this?

Q. Where can I study this more deeply?

이 글이 도움이 되셨나요?

이 글의 핵심

Introduction

”DP Problems Are Patterns”

Most DP problems are variations of a few patterns. Master the patterns and new problems become easy.

1. 1D DP Patterns

Pattern 1: Using Previous Values

Pattern 2: Max/Min Selection

2. 2D DP Patterns

Pattern 1: Grid Paths

Pattern 2: LCS (Longest Common Subsequence)

3. Knapsack Problem Patterns

0-1 Knapsack

Unbounded Knapsack

4. LIS (Longest Increasing Subsequence)

O(n²) Solution

O(n log n) Solution

5. Edit Distance Pattern

6. Practical Tips

DP Pattern Recognition

Debugging Tips

Common Mistakes

7. Advanced Patterns

Partition DP

State Machine DP

Summary

Key Points

Pattern Checklist

Recommended Problems

Baekjoon

LeetCode

Programmers

Related Posts

Keywords

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

Q. What should I read before this?

Q. Where can I study this more deeply?

Related Articles (Internal Links)

Keywords Covered in This Article (Related Search Terms)

이 글이 도움이 되셨나요?