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
Frequently Asked Questions (FAQ)
Q. When would I use this in practice?
A. Complete guide to dynamic programming for coding interviews. Master memoization, tabulation, and DP patterns with princi…
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.
Related Articles (Internal Links)
Other articles related to this topic.
- 그리디 알고리즘 | 매 순간 최선 탐욕 알고리즘 완벽 정리
- 백트래킹 | 모든 경우의 수 탐색 알고리즘 완벽 정리
- DP Patterns | Dynamic Programming Problem-Solving Strategies
Keywords Covered in This Article (Related Search Terms)
This article covers Algorithm, DP, Dynamic Programming, Memoization, Coding Interview.