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.

[2026] 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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): 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

다음은 python를 활용한 상세한 구현 코드입니다. 에러 처리를 통해 안정성을 확보합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

[2026] 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

이 글의 핵심

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