Dynamic Programming (DP) — Complete Guide
이 글의 핵심
Complete guide to dynamic programming for coding interviews. Master memoization, tabulation, and DP patterns with principles and code examples.
Introduction
”Don’t Repeat the Same Calculation”
Dynamic Programming (DP) stores duplicate calculations to optimize O(2ⁿ) → O(n).
1. DP Basics
Understanding with Fibonacci
Problem: Find nth Fibonacci number
# ❌ Naive recursion (O(2ⁿ) - very slow!)
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
print(fib_naive(40)) # Takes tens of seconds!Problem: Same values calculated multiple times
fib(5)
├─ fib(4)
│ ├─ fib(3)
│ │ ├─ fib(2) ← Duplicate!
│ │ └─ fib(1)
│ └─ fib(2) ← Duplicate!
└─ fib(3) ← Duplicate!
├─ fib(2)
└─ fib(1)2. Top-Down (Memoization)
Recursion + Caching
Memoization stores computed fib(k) values in a dictionary, retrieving stored values instead of recalculating. Like memorizing phone numbers instead of looking them up each time.
# ✅ Memoization (O(n))
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(40)) # Instant! (<0.001s)
# Naive vs Memoization:
# fib_naive(40): 2^40 ≈ 1 trillion calculations (tens of seconds)
# fib_memo(40): 40 calculations (instant)Memoization Caution:
# ❌ Wrong: memo as default argument
def fib_bad(n, memo={}):
# Default arguments created once at function definition
# Shared across multiple calls
pass
# ✅ Correct: memo as None
def fib_good(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_good(n-1, memo) + fib_good(n-2, memo)
return memo[n]Python Decorator
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1:
return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_cached(100)) # Very fast3. Bottom-Up (Tabulation)
Iteration + Table
Bottom-up solves small problems first, filling table sequentially:
# ✅ Bottom-Up (O(n), faster than recursion)
def fib_dp(n):
if n <= 1:
return n
# DP table
dp = [0] * (n + 1)
# Initial values
dp[0] = 0
dp[1] = 1
# Solve from small to large
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib_dp(100)) # InstantTop-Down vs Bottom-Up:
# Top-Down (Memoization)
# Pros:
# - Intuitive with recursion
# - Computes only needed values
# Cons:
# - Recursion overhead
# - Stack overflow risk
# - Relatively slower
# Bottom-Up (Tabulation)
# Pros:
# - Faster with iteration
# - No stack overflow
# - Easy space optimization
# Cons:
# - Computes all subproblems
# - Recurrence relation may be harder to find
# Bottom-up more common in practiceSpace Optimization
# ✅ O(1) space
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
print(fib_optimized(100))4. DP Problem Patterns
Pattern 1: 1D DP
Example: Climbing Stairs
def climb_stairs(n):
"""
Count ways to climb n stairs (1 or 2 steps at a time)
n=1: 1 way (1 step)
n=2: 2 ways (1+1, 2)
n=3: 3 ways (1+1+1, 1+2, 2+1)
"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(climb_stairs(5)) # 8Space Optimized:
def climb_stairs_optimized(n):
if n <= 2:
return n
prev2, prev1 = 1, 2
for i in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1Pattern 2: 2D DP
Example: Minimum Path Sum
def min_path_sum(grid):
"""
Find minimum sum path from (0,0) to (n-1,m-1)
"""
n, m = len(grid), len(grid[0])
dp = [[0] * m for _ in range(n)]
dp[0][0] = grid[0][0]
# First row
for j in range(1, m):
dp[0][j] = dp[0][j-1] + grid[0][j]
# First column
for i in range(1, n):
dp[i][0] = dp[i-1][0] + grid[i][0]
# Rest
for i in range(1, n):
for j in range(1, m):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[n-1][m-1]
# Test
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
print(min_path_sum(grid)) # 7 (1→3→1→1→1)Pattern 3: Knapsack Problem
def knapsack(weights, values, capacity):
"""
0-1 Knapsack problem
Problem: Maximize value within capacity
Constraint: Each item can be taken 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):
# Choice 1: Don't take item i
dp[i][w] = dp[i-1][w]
# Choice 2: Take item i
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(weights, values, capacity)) # 10Space Optimized (1D array):
def knapsack_optimized(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
# Update from back 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]5. DP Problem Approach
Step 1: Identify DP
✅ DP signals:
- "max/min value"
- "count ways"
- "is possible"
- Overlapping subproblems
❌ Not DP:
- Solvable with greedy
- Simple simulationStep 2: Define Recurrence
# Example: Climbing stairs
# dp[i] = ways to reach stair i
# dp[i] = dp[i-1] + dp[i-2]Step 3: Set Initial Values
# Example: Climbing stairs
dp[1] = 1 # 1 stair: 1 way
dp[2] = 2 # 2 stairs: 2 waysStep 4: Choose Implementation
# Top-Down: When recursion is natural
# Bottom-Up: When iteration is clear (faster)6. Common DP Problems
Longest Increasing Subsequence (LIS)
def length_of_lis(nums):
"""
Find length of longest increasing subsequence
[10, 9, 2, 5, 3, 7, 101, 18] → 4 ([2, 3, 7, 101])
"""
if not nums:
return 0
n = len(nums)
dp = [1] * n # Each element is a subsequence of length 1
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)
# Test
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums)) # 4Coin Change
def coin_change(coins, amount):
"""
Find minimum coins needed to make amount
coins=[1,2,5], amount=11 → 3 (5+5+1)
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Test
print(coin_change([1, 2, 5], 11)) # 3Summary
Key Points
- DP: Store duplicate calculations, O(2ⁿ) → O(n)
- Top-Down: Recursion + memoization
- Bottom-Up: Iteration + table (faster)
- Recurrence: dp[i] = f(dp[i-1], dp[i-2], …)
Problem Identification
| Signal | Example |
|---|---|
| ”Maximum/Minimum” | Max profit, min cost |
| ”Count ways” | Number of paths |
| ”Is possible” | Can reach target |
| Overlapping subproblems | Fibonacci, LCS |
Recommended Problems
Beginner
- LeetCode 70: Climbing Stairs
- LeetCode 509: Fibonacci Number
- LeetCode 746: Min Cost Climbing Stairs
Intermediate
- LeetCode 322: Coin Change
- LeetCode 300: Longest Increasing Subsequence
- LeetCode 64: Minimum Path Sum
Advanced
- LeetCode 72: Edit Distance
- LeetCode 312: Burst Balloons
- LeetCode 1143: Longest Common Subsequence
Related Posts
- DP Patterns | Problem-Solving Strategies
- Greedy Algorithms | Complete Guide
- Backtracking | Exhaustive Search
Keywords
Dynamic Programming, DP, Memoization, Tabulation, Top-Down, Bottom-Up, Fibonacci, Knapsack, LIS, Coding Interview, Algorithm, Optimization
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. Complete guide to dynamic programming for coding interviews. Master memoization, tabulation, and DP patterns with princi… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- 그리디 알고리즘 | 매 순간 최선 탐욕 알고리즘 완벽 정리
- 백트래킹 | 모든 경우의 수 탐색 알고리즘 완벽 정리
- [DP Patterns | Dynamic Programming Problem-Solving Strategies](/en/blog/algorithm-series-13-dp-patterns/
이 글에서 다루는 키워드 (관련 검색어)
Algorithm, DP, Dynamic Programming, Memoization, Coding Interview 등으로 검색하시면 이 글이 도움이 됩니다.