dp[state] = combine(dp[subproblems]) -- define the state, write the recurrence, fill the table.| DP Pattern | Time | Space | Classic Problems | Key Insight |
|---|---|---|---|---|
| 1D Linear | O(n) or O(n*k) | O(n) or O(1) | Fibonacci, Climbing Stairs, House Robber | Each state depends on a fixed number of previous states |
| 2D Grid | O(m*n) | O(m*n) or O(n) | Unique Paths, Minimum Path Sum, Dungeon Game | State = (row, col); transitions from adjacent cells |
| 0/1 Knapsack | O(n*W) | O(n*W) or O(W) | Subset Sum, Partition Equal Subset, Target Sum | Each item used at most once; iterate items then capacity |
| Unbounded Knapsack | O(n*W) | O(W) | Coin Change, Rod Cutting, Integer Break | Items reusable; iterate capacity then items (or same direction) |
| LCS | O(m*n) | O(m*n) or O(n) | Edit Distance, Shortest Common Supersequence | dp[i][j] = match/mismatch on s1[i] vs s2[j] |
| LIS | O(n log n) | O(n) | Patience Sorting, Russian Doll Envelopes | Binary search on tails array for O(n log n) |
| Interval DP | O(n^3) | O(n^2) | Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning | Merge smaller intervals; enumerate split point k |
| Bitmask DP | O(2^n * n) | O(2^n) | TSP, Assignment Problem, Hamiltonian Path | Bitmask encodes subset; n <= 20 |
| Digit DP | O(d * tight * state) | O(d * tight * state) | Count numbers with digit sum = k, Numbers without consecutive 1s | Process digits left to right with tight constraint |
| Tree DP | O(n) | O(n) | Diameter, Max Path Sum, Independent Set on Tree | Post-order traversal; merge child subtree results |
| State Machine DP | O(n * states) | O(states) | Best Time to Buy/Sell Stock (all variants), String editing with modes | Finite states with explicit transitions per step |
| Profile DP (Broken Profile) | O(n * 2^m) | O(2^m) | Domino/Tromino Tiling, Grid coloring with constraints | Encode column boundary as bitmask; m <= 20 |
START: Does the problem have overlapping subproblems?
|-- NO --> Not a DP problem. Try greedy, divide & conquer, or brute force.
|-- YES --> Does it have optimal substructure?
|-- NO --> DP won't yield optimal solution. Try brute force with pruning.
|-- YES --> Choose DP approach:
|-- Can you define states easily from the end?
| |-- YES --> Use bottom-up tabulation (iterative, no stack risk)
| |-- NO --> Use top-down memoization (recursive, natural for trees/DAGs)
|
|-- Identify the pattern:
|-- Single sequence/array? --> 1D Linear DP or LIS
|-- Two sequences to compare? --> LCS / Edit Distance (2D)
|-- Grid traversal? --> 2D Grid DP
|-- Items with weight/value, capacity limit?
| |-- Each item once? --> 0/1 Knapsack
| |-- Items reusable? --> Unbounded Knapsack
|-- Merging ranges or splitting? --> Interval DP
|-- Small set (n <= 20) with subset tracking? --> Bitmask DP
|-- Count integers in [L, R] with digit property? --> Digit DP
|-- Tree structure? --> Tree DP (post-order DFS)
|-- Multiple modes/states per step? --> State Machine DP
|-- None of the above? --> Define custom state; check for DAG structureVerify the problem has both properties: (a) overlapping subproblems -- solving it recursively would recompute the same subproblem multiple times, and (b) optimal substructure -- the optimal solution to the problem contains optimal solutions to its subproblems. [src1]
Verify: Draw the recursion tree for a small input. If you see repeated nodes, DP applies.
The state is the minimum set of variables that uniquely describes a subproblem. Common states: dp[i] (position in array), dp[i][j] (two pointers or grid position), dp[i][w] (item index + remaining capacity), dp[mask] (subset bitmask). [src1]
Verify: Can you express the answer to the original problem in terms of your state? e.g., answer = dp[n] or dp[n][W].
Express dp[state] in terms of smaller subproblems. This is the core mathematical insight. Example for 0/1 Knapsack: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]). [src1]
Verify: Manually trace the recurrence on a 3-4 element input to confirm correctness.
Identify the smallest subproblems that can be solved directly. Examples: dp[0] = 0 (no items), dp[0][0] = 1 (empty subset sums to 0), dp[leaf] = leaf.val (tree leaf). [src5]
Verify: Base cases should prevent out-of-bounds access and produce correct answers for trivial inputs.
Top-down (memoization): Write the recursive solution, add a cache (hash map or array). Natural for tree DP and problems where not all states are visited. Bottom-up (tabulation): Fill the DP table iteratively in topological order. Better for space optimization and avoiding stack overflow. [src6]
Verify: Both approaches should produce identical results on test cases.
Check if dp[i] only depends on dp[i-1] (or a fixed window). If so, reduce from O(n*m) to O(m) with a rolling array. For 1D DP depending on dp[i-1] and dp[i-2], reduce to O(1) with two variables. [src4]
Verify: Run optimized version against full-table version on test cases; results must match.
# Input: weights = [2, 3, 4, 5], values = [3, 4, 5, 6], capacity = 8
# Output: Maximum value achievable = 10
def knapsack_01(weights, values, capacity):
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], dp[w - weights[i]] + values[i])
return dp[capacity]# Input: s1 = "abcde", s2 = "ace"
# Output: Length of LCS = 3 ("ace")
def lcs(s1, s2):
m, n = len(s1), len(s2)
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev, curr = curr, [0] * (n + 1)
return prev[n]# Input: coins = [1, 5, 10, 25], amount = 30
# Output: Minimum coins needed = 2 (5 + 25)
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// Input: word1 = "horse", word2 = "ros"
// Output: Minimum operations = 3
function editDistance(word1, word2) {
const m = word1.length, n = word2.length;
let prev = Array.from({length: n + 1}, (_, j) => j);
for (let i = 1; i <= m; i++) {
const curr = [i];
for (let j = 1; j <= n; j++) {
if (word1[i-1] === word2[j-1]) {
curr[j] = prev[j-1];
} else {
curr[j] = 1 + Math.min(prev[j-1], prev[j], curr[j-1]);
}
}
prev = curr;
}
return prev[n];
}# Top-down (memoization)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n - 1) + fib_memo(n - 2)
# Bottom-up (tabulation, O(1) space)
def fib_tab(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b# BAD -- exponential O(2^n) time, recomputes same subproblems
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2)# GOOD -- O(n) time with memoization
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2)# BAD -- forward iteration allows using same item multiple times
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(weights[i], capacity + 1): # WRONG: forward
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])# GOOD -- reverse iteration ensures each item used at most once
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i] - 1, -1): # RIGHT: reverse
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])# BAD -- dp[0] = 0 means "zero ways to make amount 0"
dp = [0] * (amount + 1)
dp[0] = 0 # WRONG for counting
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]
# Result: always 0# GOOD -- exactly one way to make amount 0: choose nothing
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]# BAD -- accessing dp[i][k] and dp[k+1][j] before they are computed
for i in range(n):
for j in range(i, n):
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost)# GOOD -- iterate by interval length so smaller intervals computed first
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost)dp[0] = base case) but input arrays are 0-indexed. Mixing indices is the #1 source of bugs. Fix: explicitly document whether dp[i] means "first i items" or "item at index i". [src5]float('inf') or INT_MAX, not 0. Fix: dp = [float('inf')] * (n+1); dp[0] = 0. [src4]sys.setrecursionlimit(n + 100) or convert to bottom-up tabulation. [src6]dp[target] without checking if it was ever updated. For coin change, dp[amount] might still be inf (no valid combination exists). Fix: always check dp[answer] != sentinel before returning. [src5]| Use When | Don't Use When | Use Instead |
|---|---|---|
| Problem has overlapping subproblems AND optimal substructure | Problem has greedy choice property (locally optimal = globally optimal) | Greedy algorithms (Dijkstra, Huffman, interval scheduling) |
| Need optimal value (min/max) or count of solutions | Need to enumerate ALL valid configurations | Backtracking with pruning |
| State space is polynomial (n, n*W, n^2, n^3) | State space is exponential and n > 25 | Branch and bound, approximation algorithms |
| Subproblems form a DAG (no cycles in dependency) | Subproblems have circular dependencies | Iterative deepening, fixed-point computation |
| Problem can be decomposed into independent subproblems | Subproblems are interdependent (changing one affects others) | Simulation, constraint programming |
@lru_cache stores results in a dictionary, which has higher constant overhead than array-based tabulation. For performance-critical code (competitive programming), prefer tabulation with pre-allocated arrays.long long / long or modular arithmetic (% 10^9 + 7). Python handles big integers natively but at the cost of speed.