Dynamic Programming Pattern
Common Dynamic Programming Patterns to solve any problem
Dynamic Programming Interview Mastery
A Pattern-Based Guide from Recursion → Memoization → Tabulation
Dynamic Programming is often taught as a collection of problems:
- Climbing Stairs
- House Robber
- Knapsack
- Coin Change
- LCS
- Edit Distance
- Longest Increasing Subsequence
- Matrix Chain Multiplication
- Stock problems
- Burst Balloons
The problem with learning DP this way is that every new problem feels like a completely new puzzle.
It isn't.
Most DP interview problems are variations of a relatively small number of state and transition patterns.
The goal of this guide is therefore not to memorize solutions.
The goal is to learn how to look at a new problem and think:
"What is my state, what are my choices, and what smaller states do those choices lead to?"
Once you can answer those questions, the code becomes much easier.
1. The DP Mental Model
At its core, DP is an optimized recursive solution.
Imagine a recursive problem:
solve(state)
/ \
choice 1 choice 2
↓ ↓
subproblem subproblemDifferent branches may eventually reach the same state:
solve(A)
/ \
solve(B) solve(C)
\ /
solve(D)Without DP, solve(D) may be calculated multiple times.
DP says:
Solve each state once and remember the answer.
There are three stages you should learn.
RECURSION
↓
Explicit Memoization
↓
Bottom-Up Tabulation
↓
Space OptimizationThe important part is that the recurrence does not fundamentally change.
We're only changing how the states are evaluated.
2. Why Use an Explicit Memo Array?
You could use Python's:
@lru_cache(None)but when learning DP, an explicit array or table is often better.
Why?
Because it forces you to answer:
What exactly is my DP state?
For example:
memo[i]means:
I have a state represented by
i.
While:
memo[i][j]means:
I need two pieces of information to completely describe the state.
This creates a direct bridge to tabulation:
Memoization Tabulation
memo[i] → dp[i]
memo[i][j] → dp[i][j]
memo[i][capacity] → dp[i][capacity]
memo[mask][i] → dp[mask][i]This is one of the most useful things to understand in DP.
Your recursive function parameters usually become your DP dimensions.
3. The Universal DP Workflow
For almost every DP problem, follow this sequence.
Step 1: Find the choices
Ask:
What decisions can I make at this point?
Examples:
Knapsack:
Take / Skip
House Robber:
Rob / Skip
Stock:
Buy / Sell / Hold
LCS:
Match / Skip
Interval DP:
Split at kStep 2: Define the state
Ask:
What information completely describes the remaining problem?
Examples:
House Robber
solve(i)
Knapsack
solve(i, capacity)
LCS
solve(i, j)
Stock
solve(i, holding)
TSP
solve(mask, city)Step 3: Write recursion
Don't worry about optimization yet.
Get the decision tree correct first.
Step 4: Add an explicit memo table
Create a table based on the state.
For example:
memo = [-1] * nor:
memo = [[-1] * W for _ in range(n)]Then:
If state already solved:
return memo[state]
Otherwise:
calculate answer
store answer
return answerStep 5: Look at the memo table
Ask:
What does each cell represent?
This is the key step before tabulation.
Step 6: Convert recursion into tabulation
Your recurrence stays the same.
Only the evaluation order changes.
Step 7: Optimize space
Only after understanding the complete DP table should you ask:
Do I actually need every previous state?
Pattern 1: 1D / Linear DP
The simplest DP pattern
The state depends primarily on one index:
dp[i]Typical problems:
- Climbing Stairs
- House Robber
- Min Cost Climbing Stairs
- Decode Ways
- Maximum Sum of Non-Adjacent Elements
How to recognize it
Look for:
- an array or string
- moving from left to right
- decisions involving nearby positions
- maximum/minimum/count
- previous states determining the current state
A common structure is:
dp[i]
↑
previous positionsExample: House Robber
You have:
[2, 7, 9, 3, 1]You cannot rob two adjacent houses.
At every house:
house i
/ \
ROB SKIP
↓ ↓
i + 2 i + 1Step 1: Recursion
Define:
solve(i)as:
Maximum money that can be obtained starting from house
i.
def rob(nums):
def solve(i):
if i >= len(nums):
return 0
take = nums[i] + solve(i + 2)
skip = solve(i + 1)
return max(take, skip)
return solve(0)The logic is correct.
But the same solve(i) states are calculated repeatedly.
Step 2: Explicit Memoization
There are only n possible meaningful states:
0, 1, 2, ..., n-1Therefore:
def rob(nums):
n = len(nums)
memo = [-1] * n
def solve(i):
if i >= n:
return 0
if memo[i] != -1:
return memo[i]
take = nums[i] + solve(i + 2)
skip = solve(i + 1)
memo[i] = max(take, skip)
return memo[i]
return solve(0)Now look at:
memo[i]It means:
The maximum money I can obtain starting from index
i.
That meaning is extremely important.
Step 3: Visualize the Memo Table
For:
[2, 7, 9, 3, 1]we conceptually have:
index: 0 1 2 3 4
memo: ? ? ? ? ?Eventually:
memo[i] = answer for state iFor example:
memo[4] = 1
memo[3] = 3
memo[2] = 10
...We are solving states recursively, but storing the answers in an array.
Step 4: Convert to Bottom-Up DP
The memo recurrence is:
memo[i] = max(
nums[i] + memo[i+2],
memo[i+1]
)So the bottom-up version is simply:
def rob(nums):
n = len(nums)
dp = [0] * (n + 2)
for i in range(n - 1, -1, -1):
dp[i] = max(
nums[i] + dp[i + 2],
dp[i + 1]
)
return dp[0]Why right to left?
Because:
dp[i]
depends on
dp[i+1] and dp[i+2]Those states must already exist.
Step 5: Space Optimization
Notice:
dp[i]
only needs
dp[i+1]
dp[i+2]So we don't need the entire array.
def rob(nums):
next1 = 0
next2 = 0
for x in reversed(nums):
current = max(
x + next2,
next1
)
next2 = next1
next1 = current
return next1The progression is:
Recursion
↓
memo[i]
↓
dp[i]
↓
two variablesPattern 2: 0/1 Knapsack
This is one of the most important DP patterns.
The fundamental structure is:
Take the current item or don't take it.
"0/1" means:
0 → don't take
1 → take onceTypical problems:
- 0/1 Knapsack
- Subset Sum
- Equal Sum Partition
- Count Subsets
- Minimum Subset Sum Difference
- Target Sum
How to recognize it
Look for:
Choose elements
+
Each element can be used at most once
+
Target / capacity / sum constraintThink:
0/1 Knapsack
Example: 0/1 Knapsack
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7At each item:
ITEM
/ \
TAKE SKIPStep 1: Recursion
Define:
solve(i, remaining)as:
Maximum value using items from index
ionward withremainingcapacity.
def knapsack(weights, values, capacity):
n = len(weights)
def solve(i, remaining):
if i == n or remaining == 0:
return 0
skip = solve(i + 1, remaining)
take = 0
if weights[i] <= remaining:
take = values[i] + solve(
i + 1,
remaining - weights[i]
)
return max(take, skip)
return solve(0, capacity)Notice:
i + 1after taking the item.
That is what makes this 0/1.
Step 2: Explicit Memoization
Our state is:
(i, remaining)Therefore we need a 2D table:
memo[i][remaining]def knapsack(weights, values, capacity):
n = len(weights)
memo = [
[-1] * (capacity + 1)
for _ in range(n)
]
def solve(i, remaining):
if i == n or remaining == 0:
return 0
if memo[i][remaining] != -1:
return memo[i][remaining]
skip = solve(i + 1, remaining)
take = 0
if weights[i] <= remaining:
take = values[i] + solve(
i + 1,
remaining - weights[i]
)
memo[i][remaining] = max(take, skip)
return memo[i][remaining]
return solve(0, capacity)Step 3: Understand the Memo Table
Conceptually:
Remaining Capacity
0 1 2 3 4 5 6 7
┌───────────────────────────────
Item 0 │ ? ? ? ? ? ? ? ?
Item 1 │ ? ? ? ? ? ? ? ?
Item 2 │ ? ? ? ? ? ? ? ?
Item 3 │ ? ? ? ? ? ? ? ?
└───────────────────────────────Every cell answers:
What is the maximum value using items from
ionward with this much capacity remaining?
This is your DP table already.
Step 4: Bottom-Up
The recurrence is:
dp[i][capacity]
= max(
skip,
take
)Because the recursive version depends on:
solve(i + 1, ...)we process items from the end toward the beginning.
One valid implementation is:
def knapsack(weights, values, capacity):
n = len(weights)
dp = [
[0] * (capacity + 1)
for _ in range(n + 1)
]
for i in range(n - 1, -1, -1):
for remaining in range(capacity + 1):
skip = dp[i + 1][remaining]
take = 0
if weights[i] <= remaining:
take = values[i] + dp[
i + 1
][remaining - weights[i]]
dp[i][remaining] = max(
take,
skip
)
return dp[0][capacity]Notice something important:
There are multiple valid ways to define the indices of a knapsack DP table.
You might also see:
dp[i][capacity]defined as using the first i items, rather than items from i onward.
Both are valid.
What matters is understanding the meaning of the state and maintaining it consistently.
Step 5: Space Optimization
Notice that:
dp[i]
only depends on
dp[i+1]Therefore we can reduce:
O(N × W)space to:
O(W)def knapsack(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for remaining in range(
capacity,
weights[i] - 1,
-1
):
dp[remaining] = max(
dp[remaining],
values[i]
+ dp[remaining - weights[i]]
)
return dp[capacity]The backward iteration is critical for 0/1 Knapsack.
It prevents the same item from being used more than once in the same iteration.
0/1 Knapsack Variations
Once the pattern is understood, several problems become simple variations.
Subset Sum
Instead of maximizing value:
Can we make target sum?Replace:
max()with:
OREqual Sum Partition
If:
total_sumis odd:
impossibleOtherwise:
target = total_sum // 2and ask:
Can we create a subset with this sum?
That is Subset Sum.
Count of Subsets
Instead of asking:
Is it possible?ask:
How many ways?The transition becomes addition:
count = skip + takeTarget Sum
Assign + or - to elements.
This can be transformed into a subset-sum formulation.
The important skill is recognizing the underlying:
Take / Don't Takestructure.
Pattern 3: Unbounded Knapsack
Unbounded Knapsack looks almost identical to 0/1 Knapsack.
The difference is:
You can use an item repeatedly.
Typical problems:
- Unbounded Knapsack
- Rod Cutting
- Coin Change
The Critical Difference
0/1:
TAKE
↓
i + 1Unbounded:
TAKE
↓
iYou stay at the same item because you can use it again.
Example: Coin Change
Coins:
[1, 2, 5]Amount:
11Goal:
Minimum number of coins.
At every coin:
COIN
/ \
TAKE SKIPStep 1: Recursion
def coinChange(coins, amount):
n = len(coins)
def solve(i, remaining):
if remaining == 0:
return 0
if i == n:
return float("inf")
skip = solve(i + 1, remaining)
take = float("inf")
if coins[i] <= remaining:
take = 1 + solve(
i,
remaining - coins[i]
)
return min(take, skip)
answer = solve(0, amount)
return -1 if answer == float("inf") else answerThe important line:
solve(i, remaining - coins[i])not:
solve(i + 1, ...)Step 2: Explicit Memoization
def coinChange(coins, amount):
n = len(coins)
memo = [
[-1] * (amount + 1)
for _ in range(n)
]
def solve(i, remaining):
if remaining == 0:
return 0
if i == n:
return float("inf")
if memo[i][remaining] != -1:
return memo[i][remaining]
skip = solve(i + 1, remaining)
take = float("inf")
if coins[i] <= remaining:
take = 1 + solve(
i,
remaining - coins[i]
)
memo[i][remaining] = min(
take,
skip
)
return memo[i][remaining]
answer = solve(0, amount)
return -1 if answer == float("inf") else answerThe table:
memo[i][remaining]means:
Minimum number of coins required using coins from
ionward to createremaining.
Step 3: Bottom-Up
We can define:
dp[amount]as:
Minimum number of coins needed to make this amount.
def coinChange(coins, amount):
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for current in range(1, amount + 1):
for coin in coins:
if coin <= current:
dp[current] = min(
dp[current],
1 + dp[current - coin]
)
return -1 if dp[amount] == float("inf") else dp[amount]Pattern 4: LCS / Two-Sequence DP
Use this pattern when a problem involves comparing two sequences.
Typical problems:
- Longest Common Subsequence
- Edit Distance
- Shortest Common Supersequence
- Longest Palindromic Subsequence
- Minimum insertions/deletions
- Sequence Pattern Matching
Example: Longest Common Subsequence
A = "abcde"
B = "ace"Answer:
"ace"Length:
3Step 1: Recursion
Define:
solve(i, j)as:
LCS between
A[i:]andB[j:].
If characters match:
A[i] == B[j]
1 + solve(i+1, j+1)Otherwise:
skip A[i]
OR
skip B[j]def lcs(a, b):
def solve(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + solve(i + 1, j + 1)
return max(
solve(i + 1, j),
solve(i, j + 1)
)
return solve(0, 0)Step 2: Explicit Memoization
The recursive state is:
(i, j)Therefore:
memo[i][j]def lcs(a, b):
m = len(a)
n = len(b)
memo = [
[-1] * n
for _ in range(m)
]
def solve(i, j):
if i == m or j == n:
return 0
if memo[i][j] != -1:
return memo[i][j]
if a[i] == b[j]:
memo[i][j] = (
1 + solve(i + 1, j + 1)
)
else:
memo[i][j] = max(
solve(i + 1, j),
solve(i, j + 1)
)
return memo[i][j]
return solve(0, 0)Step 3: Understand the Table
B
a c e
┌──────────
A a │ ? ? ?
b │ ? ? ?
c │ ? ? ?
d │ ? ? ?
e │ ? ? ?
└──────────Each cell means:
LCS of the suffixes beginning at
(i, j).
This tells us exactly what the DP table represents.
Step 4: Bottom-Up
Because:
dp[i][j]
depends on
dp[i+1][j]
dp[i][j+1]
dp[i+1][j+1]we process from:
bottom-right → top-leftdef lcs(a, b):
m = len(a)
n = len(b)
dp = [
[0] * (n + 1)
for _ in range(m + 1)
]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if a[i] == b[j]:
dp[i][j] = (
1 + dp[i + 1][j + 1]
)
else:
dp[i][j] = max(
dp[i + 1][j],
dp[i][j + 1]
)
return dp[0][0]Step 5: Space Optimization
Each row only needs the next row.
Therefore:
O(MN)can become:
O(N)using a rolling array.
The important thing is to understand the full 2D table first.
LCS Family
Once the state is understood, many problems become variations.
LCS
│
├── Shortest Common Supersequence
├── Edit Distance
├── Longest Palindromic Subsequence
├── Minimum Insertions
├── Minimum Deletions
└── Sequence Pattern MatchingFor example:
LPS(s)
=
LCS(s, reverse(s))The important recognition skill is:
Two sequences + comparing positions → think LCS family.
Pattern 5: Grid DP
Grid DP appears when movement through a matrix determines the answer.
Typical problems:
- Unique Paths
- Unique Paths II
- Minimum Path Sum
- Maximum Path Sum
- Dungeon Game
Example: Unique Paths
A robot starts at:
(0, 0)and wants to reach:
(m-1, n-1)Allowed movements:
→
↓At each cell:
CELL
/ \
↓ →Step 1: Recursion
def uniquePaths(m, n):
def solve(r, c):
if r == m - 1 and c == n - 1:
return 1
if r >= m or c >= n:
return 0
return (
solve(r + 1, c)
+ solve(r, c + 1)
)
return solve(0, 0)Step 2: Memoization
State:
(r, c)Therefore:
memo[r][c]def uniquePaths(m, n):
memo = [
[-1] * n
for _ in range(m)
]
def solve(r, c):
if r == m - 1 and c == n - 1:
return 1
if r >= m or c >= n:
return 0
if memo[r][c] != -1:
return memo[r][c]
memo[r][c] = (
solve(r + 1, c)
+ solve(r, c + 1)
)
return memo[r][c]
return solve(0, 0)Step 3: Understand the Table
c →
0 1 2 3
┌───────────────
r 0│ ? ? ? ?
↓ 1│ ? ? ? ?
2│ ? ? ? ?
3│ ? ? ? ?Each cell represents:
Number of ways to reach the destination from this cell.
Step 4: Bottom-Up
Since:
dp[r][c]
depends on
dp[r+1][c]
dp[r][c+1]we process from:
bottom-right → top-leftdef uniquePaths(m, n):
dp = [
[0] * n
for _ in range(m)
]
dp[m - 1][n - 1] = 1
for r in range(m - 1, -1, -1):
for c in range(n - 1, -1, -1):
if r == m - 1 and c == n - 1:
continue
down = dp[r + 1][c] if r + 1 < m else 0
right = dp[r][c + 1] if c + 1 < n else 0
dp[r][c] = down + right
return dp[0][0]Pattern 6: Longest Increasing Subsequence
LIS problems ask for the longest subsequence satisfying an ordering condition.
Examples:
- Longest Increasing Subsequence
- Longest Decreasing Subsequence
- Russian Doll Envelopes
- Maximum Length Chain
Example
[10, 9, 2, 5, 3, 7, 101, 18]One LIS is:
2 → 3 → 7 → 101A Useful State
Define:
solve(i, previous)meaning:
Best increasing subsequence we can build starting from
i, given the previously selected element.
Choices:
SKIP nums[i]
or
TAKE nums[i]
if nums[i] > previousStep 1: Recursion
def lis(nums):
def solve(i, prev):
if i == len(nums):
return 0
skip = solve(i + 1, prev)
take = 0
if prev == -1 or nums[i] > nums[prev]:
take = 1 + solve(i + 1, i)
return max(take, skip)
return solve(0, -1)Step 2: Memoization
The state is:
(i, prev)So:
memo[i][prev + 1]We use prev + 1 because prev = -1 is a valid state.
def lis(nums):
n = len(nums)
memo = [
[-1] * (n + 1)
for _ in range(n)
]
def solve(i, prev):
if i == n:
return 0
key = prev + 1
if memo[i][key] != -1:
return memo[i][key]
skip = solve(i + 1, prev)
take = 0
if prev == -1 or nums[i] > nums[prev]:
take = 1 + solve(i + 1, i)
memo[i][key] = max(
take,
skip
)
return memo[i][key]
return solve(0, -1)Step 3: Bottom-Up
There is another useful state definition:
dp[i]
=
length of LIS ending at iThen:
def lis(nums):
n = len(nums)
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(
dp[i],
dp[j] + 1
)
return max(dp)This is an important lesson:
The same problem can have multiple valid DP state definitions.
You don't have to reproduce one particular table.
You need a state that contains enough information to calculate the answer.
Pattern 7: State Machine DP
This pattern appears heavily in stock problems.
The key idea:
Your state includes both a position and a condition.
For example:
(day, holding)where:
holding = 0 → don't own stock
holding = 1 → own stockExample: Stock II
At every day:
If NOT holding:
Buy
Skip
If holding:
Sell
HoldVisualize:
BUY
┌─────────────┐
↓ │
NOT HOLDING HOLDING
↑ │
└──── SELL ───┘Step 1: Recursion
def maxProfit(prices):
def solve(i, holding):
if i == len(prices):
return 0
skip = solve(i + 1, holding)
if holding:
sell = prices[i] + solve(
i + 1,
0
)
return max(skip, sell)
buy = -prices[i] + solve(
i + 1,
1
)
return max(skip, buy)
return solve(0, 0)Step 2: Memoization
State:
(i, holding)Therefore:
memo[i][holding]def maxProfit(prices):
n = len(prices)
memo = [
[-1] * 2
for _ in range(n)
]
def solve(i, holding):
if i == n:
return 0
if memo[i][holding] != -1:
return memo[i][holding]
skip = solve(i + 1, holding)
if holding:
sell = prices[i] + solve(
i + 1,
0
)
memo[i][holding] = max(
skip,
sell
)
else:
buy = -prices[i] + solve(
i + 1,
1
)
memo[i][holding] = max(
skip,
buy
)
return memo[i][holding]
return solve(0, 0)Step 3: Bottom-Up
The recurrence depends on:
i + 1so we process days backwards.
def maxProfit(prices):
n = len(prices)
dp = [
[0] * 2
for _ in range(n + 1)
]
for i in range(n - 1, -1, -1):
dp[i][0] = max(
dp[i + 1][0],
-prices[i] + dp[i + 1][1]
)
dp[i][1] = max(
dp[i + 1][1],
prices[i] + dp[i + 1][0]
)
return dp[0][0]This pattern extends to:
- transaction fees
- cooldown
- limited transactions
- multiple transactions
The state simply gains more dimensions when necessary.
Pattern 8: Interval DP / Matrix Chain Multiplication
This pattern appears when the problem asks you to solve a range:
[i ... j]and try every possible partition:
[i ... k] [k+1 ... j]Typical problems:
- Matrix Chain Multiplication
- Burst Balloons
- Palindrome Partitioning
- Boolean Parenthesization
- Optimal BST
- interval games
The Recognition Pattern
Whenever you see:
solve(i, j)
for k in range(i, j):
solve(i, k)
solve(k+1, j)think:
Interval DP
Matrix Chain Multiplication
Suppose matrices must be multiplied.
Different parenthesizations have different costs:
(A × B) × C
vs.
A × (B × C)Step 1: Recursion
def matrixChain(arr):
def solve(i, j):
if i >= j:
return 0
answer = float("inf")
for k in range(i, j):
left = solve(i, k)
right = solve(k + 1, j)
cost = (
arr[i - 1]
* arr[k]
* arr[j]
)
answer = min(
answer,
left + right + cost
)
return answer
return solve(1, len(arr) - 1)Step 2: Memoization
State:
(i, j)Therefore:
memo[i][j]def matrixChain(arr):
n = len(arr)
memo = [
[-1] * n
for _ in range(n)
]
def solve(i, j):
if i >= j:
return 0
if memo[i][j] != -1:
return memo[i][j]
answer = float("inf")
for k in range(i, j):
cost = (
solve(i, k)
+ solve(k + 1, j)
+ arr[i - 1]
* arr[k]
* arr[j]
)
answer = min(
answer,
cost
)
memo[i][j] = answer
return answer
return solve(1, n - 1)Step 3: Understand the Table
j →
0 1 2 3 4
┌────────────────
i 0│
↓ 1│ ? ? ? ?
2│ ? ? ?
3│ ? ?
4│ ?Only states where:
i < jmatter.
Each cell represents:
Minimum cost to solve the interval
[i, j].
Step 4: Bottom-Up
An interval depends on smaller intervals.
Therefore we process:
length = 2
length = 3
length = 4
...def matrixChain(arr):
n = len(arr)
dp = [
[0] * n
for _ in range(n)
]
for length in range(2, n):
for i in range(1, n - length + 1):
j = i + length - 1
dp[i][j] = float("inf")
for k in range(i, j):
cost = (
dp[i][k]
+ dp[k + 1][j]
+ arr[i - 1]
* arr[k]
* arr[j]
)
dp[i][j] = min(
dp[i][j],
cost
)
return dp[1][n - 1]The key visualization:
[ i ................ j ]
↓
choose k
/ \
[i...k] [k+1...j]Pattern 9: Tree DP
Tree DP works by solving children first and passing information upward.
node
/ \
left right
↓ ↓
result result
\ /
nodeTypical problems:
- Diameter of Binary Tree
- Maximum Path Sum
- House Robber III
- Binary Tree Cameras
- Tree independent set
Example: Diameter
At each node:
left height
right heightThe path through the current node is:
left + rightThe value returned to the parent is:
1 + max(left, right)Step 1: Recursion
def diameter(root):
answer = 0
def solve(node):
nonlocal answer
if not node:
return 0
left = solve(node.left)
right = solve(node.right)
answer = max(
answer,
left + right
)
return 1 + max(left, right)
solve(root)
return answerTree DP often naturally becomes memoized by the recursion itself because each node is normally visited once.
For more complex tree DP, however, the state may be:
memo[node][state]For example:
state = whether the parent is selectedPattern 10: DAG / Graph DP
A Directed Acyclic Graph provides a natural dependency order.
Example:
A → B → D
\ ↑
→ C ───┘If:
u → vthen v can depend on the answer calculated for u.
Longest Path in DAG
A common transition is:
dp[v] = max(
dp[v],
dp[u] + weight
)You can solve this recursively with memoization or iteratively using topological order.
Recursive
def solve(node):
if node in memo:
return memo[node]
answer = 0
for neighbor, weight in graph[node]:
answer = max(
answer,
weight + solve(neighbor)
)
memo[node] = answer
return answerThe state is simply:
nodeBottom-Up
Get a topological ordering:
for u in topo_order:
for v, weight in graph[u]:
dp[v] = max(
dp[v],
dp[u] + weight
)The important recognition:
DAG + optimization/counting over paths often means Graph DP.
Pattern 11: Bitmask DP
Bitmask DP is useful when the state must remember:
Which elements have already been used?
Suppose:
A B C Dand:
mask = 0101means:
A → used
B → unused
C → used
D → unusedThe state often becomes:
dp[mask][i]meaning:
We have visited the elements represented by
maskand currently stand ati.
Example: Traveling Salesman
At each city:
Go to an unvisited cityRecursive
def solve(mask, city):
if mask == all_visited:
return cost[city][0]
answer = float("inf")
for nxt in range(n):
if not (mask & (1 << nxt)):
new_mask = mask | (1 << nxt)
answer = min(
answer,
cost[city][nxt]
+ solve(new_mask, nxt)
)
return answerMemoization
memo = [
[-1] * n
for _ in range(1 << n)
]Then:
def solve(mask, city):
if mask == all_visited:
return cost[city][0]
if memo[mask][city] != -1:
return memo[mask][city]
answer = float("inf")
for nxt in range(n):
if not (mask & (1 << nxt)):
answer = min(
answer,
cost[city][nxt]
+ solve(
mask | (1 << nxt),
nxt
)
)
memo[mask][city] = answer
return answerThe number of states is approximately:
2^N × Nso this is generally appropriate only for relatively small N.
Pattern 12: Digit DP
Digit DP is an advanced but powerful pattern.
Use it when the problem asks you to count numbers satisfying a digit-related property.
Examples:
- Count numbers with a particular digit sum
- Count numbers without repeated digits
- Count numbers satisfying digit constraints
- Count valid numbers between two bounds
A typical state might be:
dp[position][tight][sum]The tight Concept
Suppose the upper bound is:
527If the first digit is:
4then the remaining digits can freely range from:
0 ... 9because:
4 < 5But if the first digit is:
5then the next digit cannot exceed:
2Therefore:
tight = Truemeans:
We are still equal to the upper bound's prefix.
And:
tight = Falsemeans:
We are already smaller, so the remaining digits are unrestricted.
The Big DP Pattern Map
Now we can organize the major interview patterns.
DP
│
┌──────────────────┼───────────────────┐
│ │ │
Sequence Selection Structure
│ │ │
↓ ↓ ↓
1D DP 0/1 Knapsack Tree DP
LIS Unbounded DAG DP
LCS Knapsack
│
↓
State DP
│
↓
Stock / GamesAnd:
Range
↓
Interval / MCM
Grid
↓
Grid DP
Used subset
↓
Bitmask DP
Number digits
↓
Digit DPThe Most Important DP Skill: Identify the State
Don't start by asking:
"Which LeetCode problem is this?"
Ask:
"What information completely describes my remaining problem?"
Examples:
House Robber
solve(i)Therefore:
dp[i]Knapsack
solve(i, capacity)Therefore:
dp[i][capacity]LCS
solve(i, j)Therefore:
dp[i][j]Stock
solve(i, holding)Therefore:
dp[i][holding]Interval DP
solve(i, j)Therefore:
dp[i][j]TSP
solve(mask, city)Therefore:
dp[mask][city]This is the connection you should train yourself to see.
How to Determine the DP Table
Your recursive parameters usually tell you the dimensions.
solve(i)
↓
dp[i]
solve(i, j)
↓
dp[i][j]
solve(i, capacity)
↓
dp[i][capacity]
solve(i, state)
↓
dp[i][state]
solve(mask, i)
↓
dp[mask][i]This is why learning memoization using explicit arrays is so useful.
You can literally see the table emerge from the recursion.
How to Determine Iteration Direction
This is one of the most important parts of converting recursion to bottom-up DP.
Look at the dependencies.
Depends on smaller index
dp[i]
depends on dp[i-1]Process:
left → rightDepends on larger index
dp[i]
depends on dp[i+1]Process:
right → leftDepends on smaller intervals
dp[i][j]
depends on:
dp[i][k]
dp[k+1][j]Process:
short intervals → long intervalsGrid
If:
dp[r][c]
depends on dp[r+1][c]
and dp[r][c+1]process:
bottom-right → top-leftMaximum, Minimum, Count or Boolean?
Once you've identified the state and choices, determine what the problem is asking.
Maximum
Keywords:
maximum
largest
longest
best
maximum profitUse:
max(...)Minimum
Keywords:
minimum
smallest
fewest
least
minimum costUse:
min(...)Count
Keywords:
how many
number of ways
countUsually:
ways = choice1 + choice2Boolean
Keywords:
possible?
can we?
is there a way?Usually:
possible = choice1 or choice2This is why:
Subset Sum
Count Subsets
Knapsackcan look very different while sharing the same underlying structure.
The Universal DP Template
When solving a new DP problem, start here:
def solve(state):
# 1. Base case
if base_case:
return base_answer
# 2. Already solved?
if memo[state] != UNVISITED:
return memo[state]
# 3. Explore choices
answer = ...
# 4. Store answer
memo[state] = answer
return answerThen convert it to:
dp = ...
# initialize base cases
# calculate states in dependency order
return dp[start_state]The Interview DP Checklist
When you see a new problem, ask:
┌─────────────────────────────────────────────┐
│ DP CHECKLIST │
└─────────────────────────────────────────────┘
1. Is the answer asking for:
maximum / minimum / count / existence?
↓
2. What are my choices?
↓
3. What variables describe the remaining problem?
↓
4. What is my recursive state?
↓
5. What are the base cases?
↓
6. Can the same state be reached repeatedly?
↓
7. Create memo[state]
↓
8. What does each memo cell mean?
↓
9. What states does it depend on?
↓
10. Use that dependency to determine
bottom-up iteration order.
↓
11. Can the table be reduced to
fewer rows / variables?DP Pattern Recognition Cheat Sheet
| If the problem says... | Think... |
|---|---|
| Sequence + previous choices | 1D DP |
| Take / Don't Take | 0/1 Knapsack |
| Items can be reused | Unbounded Knapsack |
| Two strings/sequences | LCS |
| Move through a matrix | Grid DP |
| Increasing subsequence | LIS |
| Buy / Sell / Hold | State Machine DP |
[i, j] + split at k |
Interval / MCM DP |
| Parent depends on children | Tree DP |
| Directed acyclic dependencies | DAG DP |
| Track which elements are used | Bitmask DP |
| Count numbers based on digits | Digit DP |
What You Should Master First
You don't need to learn all patterns equally.
Tier 1 — Essential
1. 1D DP
2. 0/1 Knapsack
3. Unbounded Knapsack
4. LCS
5. Grid DP
6. LISThese build the fundamental DP intuition.
Tier 2 — Important
7. State Machine DP
8. Interval / MCM DP
9. Tree DPThese cover many medium and hard interview problems.
Tier 3 — Advanced
10. DAG DP
11. Bitmask DP
12. Digit DPLearn these after the fundamentals are comfortable.
How to Practice
For every new DP pattern, don't immediately memorize the optimized solution.
Use this progression:
PROBLEM
│
↓
Draw the choices
│
↓
Recursion
│
↓
Identify recursive parameters
│
↓
Create explicit memo table
│
↓
Understand what each cell means
│
↓
Convert to bottom-up DP
│
↓
Determine direction
│
↓
Optimize the spaceFor each pattern, solve several problems while forcing yourself to follow this process.
The Real Goal
The biggest improvement in DP comes when you stop asking:
"Have I seen this exact problem before?"
and start asking:
"What state am I in?"
These problems may look completely unrelated:
House Robber
Knapsack
LCS
Stock Trading
Matrix Chain Multiplication
TSPBut their underlying states are:
House Robber
→ dp[i]
Knapsack
→ dp[i][capacity]
LCS
→ dp[i][j]
Stock
→ dp[i][holding]
MCM
→ dp[i][j]
TSP
→ dp[mask][city]Once you can identify that state, the rest follows:
Identify State
↓
Identify Choices
↓
Write Recursion
↓
Add Explicit Memoization
↓
Understand Memo Table
↓
Convert to Tabulation
↓
Optimize SpaceThat is the skill that turns Dynamic Programming from a collection of tricks into a repeatable problem-solving process.
Final Takeaway
You don't need to memorize hundreds of DP solutions.
You need to become comfortable with this transformation:
RECURSION
│
│
"What are my choices?"
│
↓
STATE
│
│
"What defines it?"
│
↓
EXPLICIT MEMO TABLE
│
│
"What does each cell mean?"
│
↓
DP TABLE
│
│
"What are the dependencies?"
│
↓
ITERATION ORDER
│
↓
SPACE OPTIMIZATIONOnce this becomes second nature, a new DP problem stops looking like a completely new problem.
You start seeing the shape of the solution.