Dynamic Programming
Patterns, Techniques & Classic Problems
1. What is Dynamic Programming?
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into
overlapping subproblems and storing the results to avoid redundant computation. A problem is a DP candidate
when it exhibits:
• Optimal Substructure — optimal solution is built from optimal solutions of subproblems.
• Overlapping Subproblems — the same subproblems are solved repeatedly.
2. Two Approaches
2.1 Top-Down (Memoization)
Recursion + caching: solve the problem recursively; cache each result the first time it is computed so
subsequent calls return in O(1).
from functools import lru_cache
# Fibonacci — top-down
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
2.2 Bottom-Up (Tabulation)
Iterative: fill a table starting from the smallest subproblems, building up to the answer. No recursion overhead;
often faster in practice.
# Fibonacci — bottom-up
def fib(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-optimised: O(1)
def fib_opt(n):
a, b = 0, 1
for _ in range(n): a, b = b, a + b
return a
3. Common DP Patterns
Pattern State Idea Examples
1-D / Linear DP State = single index Climbing stairs, house robber
2-D Grid DP State = (row, col) Unique paths, min path sum
Knapsack (0/1) State = (item, capacity) 0/1 Knapsack, subset sum
Unbounded Knapsack Items reusable Coin change, rod cutting
Longest Common Subseq State = (i, j) on two strings LCS, edit distance, LIS
Interval DP State = (l, r) subarray Matrix chain mult., burst balloons
Tree DP State = node + subtree info Max path sum, diameter
Bitmask DP State = bitmask of subsets TSP, assignment problems
Digit DP State = digit position + flags Count numbers with property
4. Classic Problems with Solutions
4.1 0/1 Knapsack
Given weights and values of n items and capacity W, find the maximum value subset.
def knapsack(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(W+1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
values[i-1] + dp[i-1][w - weights[i-1]])
return dp[n][W] # O(n*W) time, O(n*W) space
4.2 Longest Common Subsequence (LCS)
def lcs(s, t):
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[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] # O(m*n) time
4.3 Coin Change (Unbounded Knapsack)
def coin_change(coins, amount):
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 -1
4.4 Longest Increasing Subsequence (LIS)
# O(n log n) with patience sorting + binary search
import bisect
def lis(nums):
tails = []
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails): [Link](x)
else: tails[pos] = x
return len(tails)
4.5 Edit Distance (Levenshtein)
def edit_distance(s, t):
m, n = len(s), len(t)
dp = list(range(n + 1))
for i in range(1, m + 1):
prev = dp[0]; dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if s[i-1] == t[j-1]: dp[j] = prev
else: dp[j] = 1 + min(prev, dp[j], dp[j-1])
prev = temp
return dp[n] # O(m*n) time, O(n) space
5. Complexity Cheat Sheet
Problem Time Space (full/opt)
Fibonacci O(n) O(n) / O(1)
0/1 Knapsack O(n*W) O(n*W) / O(W)
Coin Change O(n*A) O(A)
LCS O(m*n) O(m*n) / O(n)
LIS (DP) O(n^2) O(n)
LIS (binary search) O(n log n) O(n)
Edit Distance O(m*n) O(m*n) / O(n)
Matrix Chain Mult. O(n^3) O(n^2)
TSP (bitmask DP) O(2^n * n^2) O(2^n * n)
6. DP Problem-Solving Framework
• Step 1 — Define the state: What does dp[i] (or dp[i][j]) represent?
• Step 2 — Recurrence: Express dp[i] in terms of smaller subproblems.
• Step 3 — Base cases: Identify the smallest valid inputs (n=0, empty string, etc.).
• Step 4 — Order: Ensure subproblems are computed before they are needed.
• Step 5 — Reconstruct: Trace back through the table to recover the actual solution.
• Optimise space: If dp[i] only depends on dp[i-1], keep only two rows / two variables.
• Top-down first: It's easier to reason about; convert to bottom-up only if needed for speed.