What is Dynamic Programming?
DP solves problems by breaking them into overlapping subproblems and storing solutions to avoid recomputation.
Key insight: Optimal solution contains optimal solutions to subproblems.
Two approaches:
- Top-Down (Memoization): Recursive + cache
- Bottom-Up (Tabulation): Iterative, fill table from base cases
Fibonacci — The Classic Example
# Naive recursive — O(2ⁿ) — terrible!
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
# Memoization — O(n) time, O(n) space
from functools import cache
@cache
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n-1) + fib_memo(n-2)
# Tabulation — O(n) time, O(n) space
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]
# Space-optimized — O(n) time, O(1) space
def fib_opt(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
1D Dynamic Programming
Climbing Stairs
def climb_stairs(n):
"""How many ways to climb n stairs (1 or 2 steps at a time)?"""
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)) # 8
House Robber
def rob(nums):
"""Max money from non-adjacent houses"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
print(rob([2, 7, 9, 3, 1])) # 12 (2+9+1)
print(rob([1, 2, 3, 1])) # 4 (1+3)
Coin Change
def coin_change(coins, amount):
"""Minimum coins to make amount"""
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
print(coin_change([1, 5, 6, 9], 11)) # 2 (5+6)
print(coin_change([2], 3)) # -1
Word Break
def word_break(s, word_dict):
"""Can s be segmented into words from word_dict?"""
n = len(s)
word_set = set(word_dict)
dp = [False] * (n + 1)
dp[0] = True # empty string is valid
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]
print(word_break("leetcode", ["leet", "code"])) # True
print(word_break("applepenapple", ["apple","pen"])) # True
print(word_break("catsandog", ["cats","dog","sand"])) # False
2D Dynamic Programming
Unique Paths
def unique_paths(m, n):
"""Number of paths in m×n grid (right or down only)"""
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
Longest Common Subsequence (LCS)
def lcs(text1, text2):
"""Length of longest common subsequence"""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[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]
print(lcs("abcde", "ace")) # 3
print(lcs("abc", "abc")) # 3
print(lcs("abc", "def")) # 0
Edit Distance
def min_distance(word1, word2):
"""Levenshtein distance — min operations to transform word1 → word2"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base cases: delete all or insert all
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
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]
print(min_distance("horse", "ros")) # 3
print(min_distance("intention", "execution")) # 5
0/1 Knapsack
def knapsack(weights, values, capacity):
"""Classic 0/1 knapsack — each item used at most once"""
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 item i
dp[i][w] = dp[i-1][w]
# Take item i (if it fits)
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]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(knapsack(weights, values, 7)) # 9
Interval DP
def burst_balloons(nums):
"""Burst balloons to maximize coins — O(n³)"""
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for left in range(0, n - length):
right = left + length
for k in range(left + 1, right):
dp[left][right] = max(
dp[left][right],
dp[left][k] + nums[left] * nums[k] * nums[right] + dp[k][right]
)
return dp[0][n-1]
print(burst_balloons([3, 1, 5, 8])) # 167
Exercises
Exercise 1: Maximum Product Subarray
Find the subarray with the maximum product.
Solution:
def max_product(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
candidates = (num, max_prod * num, min_prod * num)
max_prod = max(candidates)
min_prod = min(candidates)
result = max(result, max_prod)
return result
print(max_product([2, 3, -2, 4])) # 6 (2*3)
print(max_product([-2, 0, -1])) # 0
Exercise 2: Longest Increasing Subsequence
Find the length of the longest strictly increasing subsequence.
Solution:
import bisect
def lis(nums):
"""O(n log n) using patience sorting"""
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)
print(lis([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,18 or 2,5,7,18)
Exercise 3: Decode Ways
Count ways to decode a string of digits (A=1, B=2, ..., Z=26).
Solution:
def num_decodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty string
dp[1] = 1 # first character
for i in range(2, n + 1):
one = int(s[i-1:i])
two = int(s[i-2:i])
if one >= 1:
dp[i] += dp[i-1]
if 10 <= two <= 26:
dp[i] += dp[i-2]
return dp[n]
print(num_decodings("12")) # 2 ("AB" or "L")
print(num_decodings("226")) # 3 ("BZ","VF","BBF")
print(num_decodings("06")) # 0