Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into simpler subproblems. It’s essential for coding interviews and real-world optimization problems.
In this guide, we’ll explore DP fundamentals, two main approaches (top-down and bottom-up), and classic problems.
Understanding Dynamic Programming
The Core Idea
┌─────────────────────────────────────────────────────────────┐
│ Dynamic Programming Concept │
│ │
│ Without DP: With DP: │
│ │
│ f(5) calls f(4), f(5) │
│ f(4) calls f(3), / \ │
│ f(3) calls f(2), f(4) f(4) ← reuse! │
│ f(2) calls f(1), / \ │
│ f(1) returns 1 f(3) f(3) │
│ / \ │
│ Exponential time! f(2) f(2) │
│ \ │
│ f(1) │
│ │
│ Time: O(2^n) Time: O(n) │
│ │
└─────────────────────────────────────────────────────────────┘
When to Use DP
# DP applies when problem has these properties:
dp_characteristics = {
"optimal_substructure": {
"description": "Solution can be built from solutions to subproblems",
"example": "Shortest path: shortest path to B + shortest B→C"
},
"overlapping_subproblems": {
"description": "Same subproblems are solved multiple times",
"example": "Fibonacci: f(3) computed multiple times"
}
}
# Common DP patterns
dp_patterns = [
"Count ways to reach position",
"Maximum/Minimum value",
"Yes/No questions (decision)",
"Sequences and substrings",
"Optimization problems"
]
Two Approaches
Top-Down (Memoization)
# Fibonacci - Memoization
from functools import lru_cache
# Using lru_cache decorator
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# Manual memoization
def fib_manual_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_manual_memo(n - 1, memo) + fib_manual_memo(n - 2, memo)
return memo[n]
Bottom-Up (Tabulation)
# Fibonacci - Tabulation
def fib_tab(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Space-optimized
def fib_optimized(n):
if n <= 1:
return n
prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
Classic DP Problems
Climbing Stairs
# Problem: Count ways to climb n stairs (1 or 2 steps at a time)
# Method 1: Memoization
@lru_cache(maxsize=None)
def climb_stairs_memo(n):
if n <= 2:
return n
return climb_stairs_memo(n - 1) + climb_stairs_memo(n - 2)
# Method 2: Tabulation
def climb_stairs_tab(n):
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]
# Method 3: Space optimized
def climb_stairs(n):
if n <= 2:
return n
prev, curr = 1, 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return curr
# Variation: Can take 1, 2, or 3 steps
def climb_stairs_k(n, k):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for step in range(1, k + 1):
if i - step >= 0:
dp[i] += dp[i - step]
return dp[n]
House Robber
# Problem: Max money without robbing adjacent houses
def rob_memo(nums):
"""Memoization"""
n = len(nums)
@lru_cache(maxsize=None)
def dp(i):
if i < 0:
return 0
return max(dp(i - 1), dp(i - 2) + nums[i])
return dp(n - 1)
def rob_tab(nums):
"""Tabulation"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
def rob_optimized(nums):
"""Space optimized"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev, curr = 0, 0
for num in nums:
prev, curr = curr, max(curr, prev + num)
return curr
# Variation: Houses in circle (cannot rob first and last)
def rob_circle(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# Rob first or don't rob first
return max(rob_optimized(nums[:-1]), rob_optimized(nums[1:]))
Longest Common Subsequence
# Problem: Find LCS length between two strings
def lcs_memo(s1, s2):
"""Memoization"""
@lru_cache(maxsize=None)
def dp(i, j):
if i == len(s1) or j == len(s2):
return 0
if s1[i] == s2[j]:
return 1 + dp(i + 1, j + 1)
return max(dp(i + 1, j), dp(i, j + 1))
return dp(0, 0)
def lcs_tab(s1, s2):
"""Tabulation"""
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] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
def lcs_backtrack(s1, s2):
"""Get actual LCS string"""
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] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Backtrack to find LCS
lcs = []
i, j = m, n
while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
lcs.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(lcs))
Longest Increasing Subsequence
# Problem: Find LIS length
def lis_memo(nums):
"""O(n²) memoization"""
@lru_cache(maxsize=None)
def dp(i, prev):
if i == len(nums):
return 0
take = 0
if nums[i] > prev:
take = 1 + dp(i + 1, nums[i])
skip = dp(i + 1, prev)
return max(take, skip)
return dp(0, float('-inf'))
def lis_tab(nums):
"""O(n²) tabulation"""
if not nums:
return 0
n = len(nums)
dp = [1] * n # LIS ending at each position
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)
def lis_binary(nums):
"""O(n log n) using binary search"""
if not nums:
return 0
import bisect
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
# To reconstruct LIS
def lis_with_reconstruction(nums):
"""Returns actual LIS"""
if not nums:
return []
import bisect
dp = [0] * len(nums) # LIS ending at each position
idx = [0] * len(nums) # Previous index
length = 0
for i in range(len(nums)):
# Binary search
lo, hi = 0, length
while lo < hi:
mid = (lo + hi) // 2
if nums[dp[mid]] < nums[i]:
lo = mid + 1
else:
hi = mid
dp[lo] = i
idx[i] = dp[lo - 1] if lo > 0 else -1
length = max(length, lo + 1)
# Reconstruct
result = [0] * length
pos = dp[length - 1]
for i in range(length - 1, -1, -1):
result[i] = nums[pos]
pos = idx[pos]
return result
0/1 Knapsack
# Problem: Max value with weight limit
def knapsack_memo(weights, values, capacity):
"""Memoization"""
n = len(weights)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == n or remaining == 0:
return 0
# Skip
skip = dp(i + 1, remaining)
# Take if possible
take = 0
if weights[i] <= remaining:
take = values[i] + dp(i + 1, remaining - weights[i])
return max(skip, take)
return dp(0, capacity)
def knapsack_tab(weights, values, capacity):
"""Tabulation"""
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):
if weights[i - 1] <= w:
dp[i][w] = max(
dp[i - 1][w],
values[i - 1] + dp[i - 1][w - weights[i - 1]]
)
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
def knapsack_optimized(weights, values, capacity):
"""Space optimized - 1D DP"""
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
return dp[capacity]
Coin Change
# Problem: Minimum coins to make amount
def coin_change_memo(coins, amount):
"""Memoization"""
@lru_cache(maxsize=None)
def dp(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
min_coins = float('inf')
for coin in coins:
result = dp(remaining - coin)
if result != float('inf'):
min_coins = min(min_coins, result + 1)
return min_coins
result = dp(amount)
return result if result != float('inf') else -1
def coin_change_tab(coins, amount):
"""Tabulation"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Variation: Count ways
def coin_change_count(coins, amount):
"""Count number of ways"""
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]
return dp[amount]
Maximum Subarray (Kadane’s)
# Problem: Maximum sum of contiguous subarray
def max_subarray(nums):
"""Kadane's algorithm"""
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
def max_subarray_with_indices(nums):
"""Also return indices"""
max_sum = current_sum = nums[0]
start = end = 0
temp_start = 0
for i in range(1, len(nums)):
if nums[i] > current_sum + nums[i]:
current_sum = nums[i]
temp_start = i
else:
current_sum += nums[i]
if current_sum > max_sum:
max_sum = current_sum
start = temp_start
end = i
return max_sum, start, end
# Variation: Maximum product
def max_product_subarray(nums):
"""Maximum product subarray"""
max_prod = min_prod = result = nums[0]
for i in range(1, len(nums)):
if nums[i] < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(nums[i], max_prod * nums[i])
min_prod = min(nums[i], min_prod * nums[i])
result = max(result, max_prod)
return result
Edit Distance
# Problem: Minimum edits to transform word1 to word2
def edit_distance(word1, word2):
"""Levenshtein distance"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base cases
for i in range(m + 1):
dp[i][0] = i # Delete all
for j in range(n + 1):
dp[0][j] = j # Insert all
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # Delete
dp[i][j - 1], # Insert
dp[i - 1][j - 1] # Replace
)
return dp[m][n]
def edit_distance_optimized(word1, word2):
"""Space optimized - 1D"""
m, n = len(word1), len(word2)
dp = list(range(n + 1))
for i in range(1, m + 1):
new_dp = [i] + [0] * n
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
new_dp[j] = dp[j - 1]
else:
new_dp[j] = 1 + min(dp[j], new_dp[j - 1], dp[j - 1])
dp = new_dp
return dp[n]
Conclusion
Dynamic Programming is a powerful technique:
- Optimal substructure: Solution built from subproblem solutions
- Overlapping subproblems: Same subproblems computed multiple times
- Two approaches: Top-down (memoization) or bottom-up (tabulation)
- Space optimization: Often can reduce O(n²) to O(n)
Practice these classic problems to recognize DP patterns in interviews.
Comments