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

2026년 3월 28일 · 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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Master DP patterns: problem-solving strategies for dynamic programming. Learn 1D DP, 2D DP, knapsack, LCS, and LIS patte… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

동적 프로그래밍(DP) | 코딩 테스트 필수 알고리즘 완벽 정리
DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
[DP Practice Problems](/en/blog/algorithm-series-14-dp-problems/

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, DP, Dynamic Programming, Patterns, Coding Interview, LCS, LIS 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

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

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