Dynamic Programming Cheat Sheet
Explains dynamic programming fundamentals, overlapping subproblems and optimal substructure, through memoization, tabulation, knapsack, and LCS examples.
2 PagesAdvancedApr 12, 2026
Core DP Concepts
The vocabulary behind every dynamic programming solution.
- Overlapping Subproblems- The same smaller subproblems are solved repeatedly in a naive recursive solution — DP caches them
- Optimal Substructure- An optimal solution can be built from optimal solutions to its subproblems
- Memoization (top-down)- Recursion plus a cache (dict/array) storing results of subproblems the first time they're computed
- Tabulation (bottom-up)- Iteratively fills a table from base cases up to the final answer, avoiding recursion overhead
- State- The set of parameters that uniquely identify a subproblem, e.g. (index, remaining_capacity) in knapsack
- Space optimization- Many DP tables only need the previous row or state, letting you reduce O(n*m) space down to O(m)
Top-Down Memoization
Turning exponential recursion into linear time.
python
def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n]fib(50) # O(n) time instead of O(2^n) with naive recursion
Bottom-Up Tabulation: 0/1 Knapsack
Building a DP table iteratively.
python
def knapsack(weights, values, capacity): 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): dp[i][w] = dp[i - 1][w] # don't take item i-1 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]knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7) # => 9
Longest Common Subsequence
A classic 2D DP problem over two sequences.
python
def lcs(a, b): m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if a[i - 1] == b[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]lcs("ABCBDAB", "BDCABA") # => 4 ("BCBA")
Bitmask DP: Traveling Salesman
Encoding a subset of visited nodes as bits so the DP state fits in an integer, enabling exponential-but-tractable subset DP.
python
def tsp(dist): n = len(dist) FULL = (1 << n) - 1 # dp[mask][i] = min cost to visit `mask` set of cities, ending at city i dp = [[float('inf')] * n for _ in range(1 << n)] dp[1][0] = 0 # start at city 0, only city 0 visited for mask in range(1 << n): for i in range(n): if not (mask & (1 << i)) or dp[mask][i] == float('inf'): continue for j in range(n): if mask & (1 << j): continue new_mask = mask | (1 << j) new_cost = dp[mask][i] + dist[i][j] if new_cost < dp[new_mask][j]: dp[new_mask][j] = new_cost return min(dp[FULL][i] + dist[i][0] for i in range(1, n))
Tree DP: Maximum Weight Independent Set
DP over a tree via post-order recursion, where each node's state depends on whether it is included.
python
from collections import defaultdictimport syssys.setrecursionlimit(10000)def max_weight_independent_set(n, weight, edges): tree = defaultdict(list) for u, v in edges: tree[u].append(v) tree[v].append(u) def dfs(node, parent): # returns (best_without_node, best_with_node) without, with_ = 0, weight[node] for child in tree[node]: if child == parent: continue c_without, c_with = dfs(child, node) without += max(c_without, c_with) # child free either way with_ += c_without # child must be excluded return without, with_ w0, w1 = dfs(0, -1) return max(w0, w1)
Space-Optimized Edit Distance
Reducing the classic O(m*n) edit-distance table to O(min(m, n)) space by keeping only two rows.
python
def edit_distance(a, b): if len(a) < len(b): a, b = b, a # ensure b is the shorter string prev = list(range(len(b) + 1)) for i in range(1, len(a) + 1): curr = [i] + [0] * len(b) for j in range(1, len(b) + 1): if a[i - 1] == b[j - 1]: curr[j] = prev[j - 1] else: curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1]) prev = curr return prev[len(b)]edit_distance("intention", "execution") # => 5
Advanced DP Patterns
Named techniques that show up once problems outgrow simple 1D/2D tables.
- Bitmask DP- Encodes a subset as an integer's bits; used for TSP-style problems where the state must track which items are used
- Digit DP- Builds numbers digit-by-digit under a tight/loose bound to count values in a range satisfying a property
- Tree DP- Post-order recursion where each subtree's DP value is combined from its children's values
- DP on DAGs (memoized longest/shortest path)- Any acyclic dependency graph can be solved with memoized recursion; the recursion order is a topological sort
- Monotonic Deque Optimization- Speeds up DP transitions of the form dp[i] = min(dp[j] + cost(j, i)) over a sliding window from O(n*k) to O(n)
- Convex Hull Trick / Li Chao Tree- Maintains a set of linear functions to answer min/max queries in O(log n), used to optimize DP with linear cost terms
- Probability / Expected Value DP- States hold probabilities or expectations instead of counts/costs; transitions sum weighted outcomes
- Matrix Exponentiation- Expresses a linear recurrence as matrix multiplication, computing the n-th term in O(k^3 log n) instead of O(n)
Matrix Exponentiation for Linear Recurrences
Computing the n-th Fibonacci number in O(log n) by exponentiating the recurrence's transition matrix.
python
def mat_mult(a, b): return [[sum(a[i][k] * b[k][j] for k in range(len(b))) for j in range(len(b[0]))] for i in range(len(a))]def mat_pow(m, power): n = len(m) result = [[1 if i == j else 0 for j in range(n)] for i in range(n)] # identity while power: if power & 1: result = mat_mult(result, m) m = mat_mult(m, m) power >>= 1 return resultdef fib(n): if n == 0: return 0 base = [[1, 1], [1, 0]] return mat_pow(base, n - 1)[0][0]fib(50) # => 12586269025, computed in O(log n) matrix multiplications
Pro Tip
When converting a recursive solution to DP, first write the naive recursion and identify the state (its arguments) — if two different call paths ever produce the same arguments, you have overlapping subproblems and DP will help.
Was this cheat sheet helpful?
Explore Topics
#DynamicProgramming#DynamicProgrammingCheatSheet#Programming#Advanced#CoreDPConcepts#TopDownMemoization#BottomUpTabulation01Knapsack#LongestCommonSubsequence#CheatSheet#SkillVeris
