Dynamic Programming: Patterns That Solve Everything
Demystify DP with 6 core patterns — linear, knapsack, string, grid, interval, and state machine. Learn to identify DP problems and build solutions from subproblems.
When Is a Problem DP?
A problem is solvable with DP when it has: (1) Optimal substructure — the optimal solution contains optimal solutions to subproblems, and (2) Overlapping subproblems — the same subproblems are solved repeatedly. If you find yourself computing the same thing multiple times in a recursive solution, DP will help.
The DP development process: (1) Define subproblems and state. (2) Write the recurrence relation. (3) Identify base cases. (4) Decide iteration order. (5) Optimize space if possible.
Pattern 1: Linear DP
State depends on previous elements in a sequence. Classic examples: climbing stairs, house robber, longest increasing subsequence. dp[i] represents the answer for the first i elements.
def longest_increasing_subsequence(nums: list[int]) -> int:
"""Length of the longest strictly increasing subsequence."""
if not nums:
return 0
# dp[i] = length of LIS ending at index i
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) # O(n²)
def lis_optimized(nums: list[int]) -> int:
"""O(n log n) using patience sorting."""
from bisect import bisect_left
tails = [] # tails[i] = smallest tail of increasing subseq of length i+1
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)Pattern 2: 0/1 Knapsack
Choose items with weights and values to maximize value within a weight limit. Each item can be taken once (0/1) or unlimited times (unbounded). dp[i][w] = max value using first i items with capacity w.
def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
"""0/1 Knapsack: each item used at most once."""
n = len(weights)
# Space-optimized: 1D array, iterate capacity backwards
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
def coin_change(coins: list[int], amount: int) -> int:
"""Minimum coins to make amount (unbounded knapsack variant)."""
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float("inf") else -10/1 knapsack iterates capacity backwards (to avoid reusing items). Unbounded knapsack iterates forwards (allowing reuse). This is the only difference!
Pattern 3: String DP
Two-string problems use a 2D table where dp[i][j] represents the answer for the first i characters of string 1 and first j characters of string 2. Classic problems: edit distance, LCS, regex matching.
def edit_distance(word1: str, word2: str) -> int:
"""Minimum operations (insert, delete, replace) to transform word1 to word2."""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
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]
def longest_common_subsequence(text1: str, text2: str) -> int:
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]Pattern 4: Grid DP
Navigate a grid from top-left to bottom-right. dp[i][j] depends on dp[i-1][j] and dp[i][j-1]. Problems: unique paths, minimum path sum, maximal square.
def unique_paths(m: int, n: int) -> int:
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[-1]
def maximal_square(matrix: list[list[str]]) -> int:
"""Find the largest square of 1s in a binary matrix."""
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_side = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i - 1][j - 1] == "1":
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_sidePattern 5: Interval DP
Solve problems over subarray intervals. dp[i][j] represents the answer for the subarray from i to j. Iterate by interval length. Classic: matrix chain multiplication, burst balloons, palindrome partitioning.
def longest_palindrome_substring(s: str) -> str:
"""Find the longest palindromic substring."""
n = len(s)
if n < 2:
return s
start, max_len = 0, 1
# dp[i][j] = True if s[i:j+1] is a palindrome
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
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] = length == 2 or dp[i + 1][j - 1]
if dp[i][j] and length > max_len:
start, max_len = i, length
return s[start:start + max_len]Pattern 6: State Machine DP
Model the problem as states and transitions. At each step, you're in one of several states, and the DP tracks the optimal value for each state. Classic: buy/sell stock with cooldown, regex matching.
def max_profit_with_cooldown(prices: list[int]) -> int:
"""Buy/sell stock with 1-day cooldown after selling."""
if len(prices) < 2:
return 0
# States: hold (own stock), sold (just sold), rest (cooldown done)
hold = -prices[0]
sold = 0
rest = 0
for price in prices[1:]:
prev_hold = hold
hold = max(hold, rest - price) # Keep holding or buy after rest
rest = max(rest, sold) # Keep resting or cooldown ends
sold = prev_hold + price # Sell what we're holding
return max(sold, rest)DP optimization: if dp[i] only depends on dp[i-1], use two variables instead of an array. If dp[i][j] only depends on the previous row, use a 1D array. This reduces space from O(n²) to O(n).