Introduction
Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into simpler subproblems. It’s essential for interview success and real-world optimization problems. This guide covers common DP patterns and when to apply each.
DP Fundamentals
When to Use DP
- Optimal Substructure: Solution can be built from optimal solutions of subproblems
- Overlapping Subproblems: Same subproblems are solved multiple times
Approaches
# 1. Top-Down (Memoization)
# - Start from problem, recursively solve subproblems
# - Cache results to avoid recomputation
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]
# 2. Bottom-Up (Tabulation)
# - Build solution from smallest subproblems
# - Usually more space-efficient
def fib_tab(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 3. Space-Optimized
# - Only keep necessary states
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
Common DP Patterns
1. Fibonacci / House Robber
def climb_stairs(n):
"""
Climbing Stairs - count ways to climb n stairs.
DP: dp[i] = dp[i-1] + dp[i-2]
"""
if n <= 2:
return n
prev1, prev2 = 2, 1
for i in range(3, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1
def house_robber(nums):
"""
House Robber - max money without robbing adjacent houses.
DP: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev1 = max(nums[0], nums[1])
prev2 = nums[0]
for i in range(2, len(nums)):
curr = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = curr
return prev1
def house_robber_circular(nums):
"""House Robber II - houses in a circle."""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
def rob(nums):
prev1 = prev2 = 0
for num in nums:
curr = max(prev1, prev2 + num)
prev2 = prev1
prev1 = curr
return prev1
return max(rob(nums[:-1]), rob(nums[1:]))
2. 0/1 Knapsack
def knapsack(weights, values, capacity):
"""
0/1 Knapsack - maximize value with weight constraint.
Time: O(n * W), Space: O(W)
"""
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
return dp[capacity]
def knapsack_2d(weights, values, capacity):
"""0/1 Knapsack with 2D DP table."""
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 subset_sum(nums, target):
"""Subset Sum - can we achieve target sum?"""
dp = {0}
for num in nums:
dp = dp | {x + num for x in dp}
return target in dp
def partition_equal_subset(nums):
"""Partition Equal Subset Sum."""
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = {0}
for num in nums:
dp = dp | {x + num for x in dp}
if target in dp:
return True
return False
3. Longest Common Subsequence (LCS)
def lcs(s1, s2):
"""
Longest Common Subsequence.
DP: dp[i][j] = length of LCS of s1[0:i] and s2[0:j]
"""
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]
def lcs_with_string(s1, s2):
"""LCS returning the actual string."""
m, n = len(s1), len(s2)
dp = [[""] * (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] + s1[i-1]
else:
dp[i][j] = dp[i-1][j] if len(dp[i-1][j]) > len(dp[i][j-1]) else dp[i][j-1]
return dp[m][n]
def longest_palindromic_subsequence(s):
"""Longest Palindromic Subsequence."""
n = len(s)
dp = [[0] * n for _ in range(n)]
# Single characters are palindromes of length 1
for i in range(n):
dp[i][i] = 1
# Fill for substrings of length 2 to n
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2 if length > 2 else 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
4. Longest Increasing Subsequence (LIS)
def lis(nums):
"""
Longest Increasing Subsequence.
Time: O(n²), Space: O(n)
Alternative: O(n log n) using binary search
"""
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
def lis_binary_search(nums):
"""LIS using binary search - O(n log n)."""
import bisect
dp = []
for num in nums:
pos = bisect.bisect_left(dp, num)
if pos == len(dp):
dp.append(num)
else:
dp[pos] = num
return len(dp)
def lis_with_path(nums):
"""LIS with actual path reconstruction."""
if not nums:
return 0, []
n = len(nums)
dp = [1] * n
parent = [-1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
parent[i] = j
max_len = max(dp)
max_idx = dp.index(max_len)
# Reconstruct path
path = []
idx = max_idx
while idx != -1:
path.append(nums[idx])
idx = parent[idx]
return max_len, path[::-1]
5. Edit Distance
def edit_distance(s1, s2):
"""
Edit Distance (Levenshtein Distance).
Operations: insert, delete, replace
Time: O(m * n), Space: O(min(m, n)) possible
"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base cases: transforming empty string
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 s1[i-1] == s2[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 min_distance_word(s1, s2):
"""Min distance with word operations."""
m, n = len(s1), len(s2)
# Only allow insert/delete (no replace)
if abs(m - n) > 1:
return False
i = j = 0
diff = 0
while i < m and j < n:
if s1[i] == s2[j]:
i += 1
j += 1
else:
diff += 1
if diff > 1:
return False
if m > n:
i += 1 # Delete from s1
elif m < n:
j += 1 # Insert in s1
else:
i += 1
j += 1
return diff + (m - i) + (n - j) <= 1
6. Coin Change
def coin_change(coins, amount):
"""
Coin Change - minimum coins to make amount.
dp[i] = minimum coins to make amount i
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
def coin_change_combinations(coins, amount):
"""Count number of ways to make amount (order matters)."""
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]
return dp[amount]
def coin_change_combinations_unique(coins, amount):
"""Count number of ways (order doesn't matter)."""
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]
return dp[amount]
def coin_change_with_path(coins, amount):
"""Coin change with actual coins used."""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
parent = [-1] * (amount + 1)
for coin in coins:
for x in range(coin, amount + 1):
if dp[x - coin] + 1 < dp[x]:
dp[x] = dp[x - coin] + 1
parent[x] = coin
if dp[amount] == float('inf'):
return -1, []
# Reconstruct
path = []
curr = amount
while curr > 0:
path.append(parent[curr])
curr -= parent[curr]
return dp[amount], path
7. Unique Paths
def unique_paths(m, n):
"""Unique paths in m x n grid (right/down moves)."""
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]
def unique_paths_with_obstacles(grid):
"""Unique paths with obstacles (1 = obstacle)."""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1 if grid[0][0] == 0 else 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
dp[i][j] = 0
elif i == 0 and j == 0:
continue
elif i == 0:
dp[i][j] = dp[i][j-1]
elif j == 0:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
def minimum_path_sum(grid):
"""Minimum path sum in grid."""
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
elif i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
8. Subarray Sum Problems
def max_subarray_sum(nums):
"""Kadane's Algorithm - max subarray sum."""
max_sum = curr_sum = nums[0]
for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sum
def max_subarray_sum_circular(nums):
"""Maximum sum circular subarray."""
def kadane(nums):
max_sum = curr = nums[0]
for num in nums[1:]:
curr = max(num, curr + num)
max_sum = max(max_sum, curr)
return max_sum
max_normal = kadane(nums)
# If all numbers are negative
if max_normal < 0:
return max_normal
# Max circular = total - min subarray
total = sum(nums)
min_subarray = kadane([-x for x in nums])
max_circular = total + min_subarray
return max(max_normal, max_circular)
def subarray_sum_equals_k(nums, k):
"""Count subarrays with sum equals k."""
count = 0
prefix_sum = 0
seen = {0: 1}
for num in nums:
prefix_sum += num
count += seen.get(prefix_sum - k, 0)
seen[prefix_sum] = seen.get(prefix_sum, 0) + 1
return count
def maximum_product_subarray(nums):
"""Maximum product subarray."""
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
if num < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(num, max_prod * num)
min_prod = min(num, min_prod * num)
result = max(result, max_prod)
return result
9. String DP Patterns
def is_interleaving(s1, s2, s3):
"""Interleaving String - is s3 formed by interleaving s1 and s2?"""
if len(s1) + len(s2) != len(s3):
return False
dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
dp[0][0] = True
for i in range(len(s1) + 1):
for j in range(len(s2) + 1):
if dp[i][j]:
if i < len(s1) and s1[i] == s3[i + j]:
dp[i + 1][j] = True
if j < len(s2) and s2[j] == s3[i + j]:
dp[i][j + 1] = True
return dp[len(s1)][len(s2)]
def word_break(s, word_dict):
"""Word Break - can string be segmented into dictionary words."""
word_set = set(word_dict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
def longest_common_substring(s1, s2):
"""Longest Common Substring (contiguous)."""
m, n = len(s1), len(s2)
result = 0
dp = [[0] * (n + 1) for _ in range(2)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i % 2][j] = dp[(i-1) % 2][j-1] + 1
result = max(result, dp[i % 2][j])
else:
dp[i % 2][j] = 0
return result
DP Problem-Solving Framework
def solve_dp_problem(problem_type, *args):
"""
Framework for approaching DP problems:
1. Identify if it's a DP problem
- Optimal substructure?
- Overlapping subproblems?
2. Define state
- What does dp[i] represent?
3. Find recurrence relation
- How to compute dp[i] from dp[i-1], dp[i-2], etc.?
4. Determine base cases
- dp[0], dp[1], empty string, etc.
5. Choose approach
- Top-down (memoization) or Bottom-up (tabulation)
6. Optimize if needed
- Space optimization
"""
pass
Summary Table
| Problem Type | State Definition | Recurrence |
|---|---|---|
| Fibonacci | dp[i] = ith fib | dp[i] = dp[i-1] + dp[i-2] |
| Knapsack | dp[w] = max value | dp[w] = max(dp[w], dp[w-weight] + value) |
| LIS | dp[i] = LIS ending at i | dp[i] = max(dp[j] + 1) for j < i |
| LCS | dp[i][j] = LCS of s1[:i], s2[:j] | dp[i][j] = dp[i-1][j-1] + 1 or max(dp[i-1][j], dp[i][j-1]) |
| Edit Distance | dp[i][j] = distance s1[:i], s2[:j] | dp[i][j] = dp[i-1][j-1] or 1 + min(dp[i-1][j], dp[i][j-1]) |
| Coin Change | dp[x] = min coins for amount x | dp[x] = min(dp[x], dp[x-coin] + 1) |
Conclusion
Dynamic Programming is a powerful technique that requires practice to master. Start with simple problems like Fibonacci and House Robber, then progress to more complex patterns. Remember to:
- First try recursive with memoization
- Convert to bottom-up for space efficiency
- Optimize space when possible
- Practice recognizing problem patterns
Comments