Dynamic Programming Examples
Examples for Common Dynamic Programming Examples
Dynamic Programming Interview Patterns
From Recursion → Memoization → Tabulation → Space Optimization
Dynamic Programming becomes much easier when you stop memorizing dp[] formulas and instead learn how to derive them.
Most DP problems follow the same progression:
Problem
↓
Identify choices
↓
Write recursion
↓
Find repeated states
↓
Add memoization
↓
Convert recursion to tabulation
↓
Optimize spaceThis guide focuses on the most common DP patterns and the problems that belong to them.
The goal is not to memorize every solution.
The goal is:
See a new problem → identify its pattern → derive the DP from recursion.
1. The Universal DP Process
Before learning individual patterns, understand this process.
Suppose we have:
def solve(state):
...The recursive function represents:
"What is the answer to the remaining problem from this state?"
If there are multiple choices:
state
/ \
choice 1 choice 2
↓ ↓
state A state Bwe calculate both and combine them.
For example:
def solve(i):
take = ...
skip = ...
return max(take, skip)If the same state is reached multiple times, recursion becomes expensive.
We cache it:
@lru_cache(None)
def solve(i):
...Now convert the recursive state directly into a DP table.
If recursion is:
solve(i)we usually get:
dp[i]If recursion is:
solve(i, j)we usually get:
dp[i][j]If recursion is:
solve(i, capacity)we usually get:
dp[i][capacity]This is the key idea:
The parameters of your recursive function usually become the dimensions of your DP table.
2. Pattern 1 — 1D / Linear DP
When to recognize it
Look for:
- arrays or strings
- decisions moving from left to right
- current answer depends on previous/future positions
- maximum/minimum/count
- "ways to reach..."
- "best answer starting from index
i"
Typical problems:
Climbing Stairs
Min Cost Climbing Stairs
House Robber
House Robber II
Decode Ways
Word BreakProblem 1: Climbing Stairs
You can climb either:
1 step
2 stepsFind the number of ways to reach step n.
Recursive
At step n, the previous step was either:
n - 1
OR
n - 2def climbStairs(n):
def solve(i):
if i == 0:
return 1
if i < 0:
return 0
return (
solve(i - 1)
+ solve(i - 2)
)
return solve(n)Memoized
The recursive state is:
iso we cache i.
from functools import lru_cache
def climbStairs(n):
@lru_cache(None)
def solve(i):
if i == 0:
return 1
if i < 0:
return 0
return (
solve(i - 1)
+ solve(i - 2)
)
return solve(n)Bottom-Up
The recursion says:
solve(i)
↓
solve(i-1)
solve(i-2)Therefore:
dp[i]
↓
dp[i-1]
dp[i-2]def climbStairs(n):
dp = [0] * (n + 1)
dp[0] = 1
if n >= 1:
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]Space Optimized
Only the previous two values are needed.
def climbStairs(n):
prev2 = 1
prev1 = 1
for _ in range(n):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev2Problem 2: House Robber
At every house:
Rob
OR
SkipIf you rob house i, you cannot rob i + 1.
Recursive
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)Memoized
from functools import lru_cache
def rob(nums):
@lru_cache(None)
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)Bottom-Up
The recursion depends on:
solve(i+1)
solve(i+2)Therefore:
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]Space Optimized
def rob(nums):
next1 = 0
next2 = 0
for money in reversed(nums):
curr = max(
money + next2,
next1
)
next2 = next1
next1 = curr
return next1Problem 3: House Robber II
The houses form a circle.
Therefore, we cannot rob both:
first
AND
lastSplit into two linear problems:
Case 1: nums[0:-1]
Case 2: nums[1:]def rob(nums):
if len(nums) == 1:
return nums[0]
def rob_linear(arr):
prev2 = 0
prev1 = 0
for money in arr:
curr = max(
prev1,
prev2 + money
)
prev2 = prev1
prev1 = curr
return prev1
return max(
rob_linear(nums[:-1]),
rob_linear(nums[1:])
)Problem 4: Decode Ways
At every position:
Decode one digit
OR
Decode two digitsRecursive state:
i = current positiondef numDecodings(s):
def solve(i):
if i == len(s):
return 1
if s[i] == '0':
return 0
answer = solve(i + 1)
if (
i + 1 < len(s)
and 10 <= int(s[i:i + 2]) <= 26
):
answer += solve(i + 2)
return answer
return solve(0)Memoization:
from functools import lru_cache
def numDecodings(s):
@lru_cache(None)
def solve(i):
if i == len(s):
return 1
if s[i] == '0':
return 0
answer = solve(i + 1)
if (
i + 1 < len(s)
and 10 <= int(s[i:i + 2]) <= 26
):
answer += solve(i + 2)
return answer
return solve(0)Bottom-up:
def numDecodings(s):
n = len(s)
dp = [0] * (n + 1)
dp[n] = 1
for i in range(n - 1, -1, -1):
if s[i] == '0':
continue
dp[i] = dp[i + 1]
if (
i + 1 < n
and 10 <= int(s[i:i + 2]) <= 26
):
dp[i] += dp[i + 2]
return dp[0]3. Pattern 2 — 0/1 Knapsack
Recognition
Think:
Take or don't take, and each item can be used once.
Common problems:
0/1 Knapsack
Subset Sum
Equal Sum Partition
Count Subsets
Minimum Subset Sum Difference
Target SumThe state usually contains:
item index
+
capacity/targetProblem 5: 0/1 Knapsack
Recursive
def knapsack(weights, values, capacity):
def solve(i, remaining):
if i == len(weights) 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 an item.
That means the item cannot be used again.
Memoized
from functools import lru_cache
def knapsack(weights, values, capacity):
@lru_cache(None)
def solve(i, remaining):
if i == len(weights) 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)Bottom-Up
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]
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][capacity]Problem 6: Subset Sum
Question:
Can we select some numbers whose sum equals
target?
Recursive
def subset_sum(nums, target):
def solve(i, remaining):
if remaining == 0:
return True
if i == len(nums):
return False
skip = solve(
i + 1,
remaining
)
take = False
if nums[i] <= remaining:
take = solve(
i + 1,
remaining - nums[i]
)
return take or skip
return solve(0, target)Memoized
from functools import lru_cache
def subset_sum(nums, target):
@lru_cache(None)
def solve(i, remaining):
if remaining == 0:
return True
if i == len(nums):
return False
if nums[i] <= remaining:
if solve(
i + 1,
remaining - nums[i]
):
return True
return solve(
i + 1,
remaining
)
return solve(0, target)Bottom-Up
def subset_sum(nums, target):
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for s in range(
target,
num - 1,
-1
):
dp[s] = (
dp[s]
or dp[s - num]
)
return dp[target]Important
For 0/1 Knapsack space optimization:
iterate backwardsbecause an item can only be used once.
Problem 7: Equal Sum Partition
If:
total sum = Swe need a subset with:
S / 2So this becomes Subset Sum.
def canPartition(nums):
total = sum(nums)
if total % 2:
return False
return subset_sum(
nums,
total // 2
)Problem 8: Count Subsets With Sum K
Same state as Subset Sum.
But instead of asking:
Can it be done?we ask:
How many ways?Therefore:
OR → +Recursive
def count_subsets(nums, target):
def solve(i, remaining):
if remaining == 0:
return 1
if i == len(nums):
return 0
answer = solve(
i + 1,
remaining
)
if nums[i] <= remaining:
answer += solve(
i + 1,
remaining - nums[i]
)
return answer
return solve(0, target)Bottom-Up
def count_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
for s in range(
target,
num - 1,
-1
):
dp[s] += dp[s - num]
return dp[target]Problem 9: Minimum Subset Sum Difference
Find the reachable subset sum closest to:
total / 2def min_subset_difference(nums):
total = sum(nums)
dp = [False] * (total + 1)
dp[0] = True
for num in nums:
for s in range(
total,
num - 1,
-1
):
dp[s] |= dp[s - num]
for s in range(
total // 2,
-1,
-1
):
if dp[s]:
return total - 2 * sProblem 10: Target Sum
Transform:
+ numbers
- numbersinto a subset-sum count problem.
def findTargetSumWays(nums, target):
total = sum(nums)
if abs(target) > total:
return 0
if (total + target) % 2:
return 0
subset = (total + target) // 2
dp = [0] * (subset + 1)
dp[0] = 1
for num in nums:
for s in range(
subset,
num - 1,
-1
):
dp[s] += dp[s - num]
return dp[subset]4. Pattern 3 — Unbounded Knapsack
The difference is simple:
0/1 Knapsack:
take → i + 1
Unbounded:
take → iBecause the item can be reused.
Common problems:
Coin Change
Coin Change II
Rod Cutting
Unbounded KnapsackProblem 11: Coin Change
Find the minimum number of coins.
Recursive
def coinChange(coins, amount):
def solve(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
answer = float('inf')
for coin in coins:
answer = min(
answer,
1 + solve(
remaining - coin
)
)
return answer
answer = solve(amount)
return (
-1
if answer == float('inf')
else answer
)Memoized
from functools import lru_cache
def coinChange(coins, amount):
@lru_cache(None)
def solve(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
answer = float('inf')
for coin in coins:
answer = min(
answer,
1 + solve(
remaining - coin
)
)
return answer
answer = solve(amount)
return (
-1
if answer == float('inf')
else answer
)Bottom-Up
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]
)Problem 12: Coin Change II
Count combinations instead of minimizing coins.
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for current in range(
coin,
amount + 1
):
dp[current] += (
dp[current - coin]
)
return dp[amount]Notice the forward iteration:
coin → can be reusedProblem 13: Rod Cutting
Rod length is the capacity.
Piece length is the weight.
Price is the value.
def rod_cutting(prices, length):
dp = [0] * (length + 1)
for piece in range(
1,
length + 1
):
for current in range(
piece,
length + 1
):
dp[current] = max(
dp[current],
prices[piece - 1]
+ dp[current - piece]
)
return dp[length]5. Pattern 4 — LCS / Two-Sequence DP
Recognition
If two sequences interact:
String A
String Bthink:
dp[i][j]Common problems:
LCS
Longest Common Substring
Edit Distance
Shortest Common Supersequence
Longest Palindromic SubsequenceProblem 14: Longest Common Subsequence
At positions i and j:
Characters match
1 + solve(i+1, j+1)Characters don't match
max(
solve(i+1,j),
solve(i,j+1)
)Recursive
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)Memoized
from functools import lru_cache
def lcs(a, b):
@lru_cache(None)
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)Bottom-Up
def lcs(a, b):
m = len(a)
n = 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] = (
1
+ dp[i - 1][j - 1]
)
else:
dp[i][j] = max(
dp[i - 1][j],
dp[i][j - 1]
)
return dp[m][n]Problem 15: Longest Common Substring
Difference from LCS:
A mismatch resets the current substring.
def longest_common_substring(a, b):
m = len(a)
n = len(b)
dp = [
[0] * (n + 1)
for _ in range(m + 1)
]
answer = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = (
1
+ dp[i - 1][j - 1]
)
answer = max(
answer,
dp[i][j]
)
return answerProblem 16: Longest Palindromic Subsequence
Use:
LPS(s) = LCS(s, reverse(s))def longest_palindromic_subsequence(s):
return lcs(
s,
s[::-1]
)Problem 17: Minimum Insertions to Make Palindrome
def min_insertions(s):
return (
len(s)
- longest_palindromic_subsequence(s)
)Problem 18: Shortest Common Supersequence
Length:
len(A) + len(B) - LCSdef shortest_common_supersequence_length(a, b):
return (
len(a)
+ len(b)
- lcs(a, b)
)Problem 19: Edit Distance
Operations:
Insert
Delete
ReplaceRecursive
def edit_distance(a, b):
def solve(i, j):
if i == len(a):
return len(b) - j
if j == len(b):
return len(a) - i
if a[i] == b[j]:
return solve(i + 1, j + 1)
return 1 + min(
solve(i + 1, j), # delete
solve(i, j + 1), # insert
solve(i + 1, j + 1) # replace
)
return solve(0, 0)Memoized
from functools import lru_cache
def edit_distance(a, b):
@lru_cache(None)
def solve(i, j):
if i == len(a):
return len(b) - j
if j == len(b):
return len(a) - i
if a[i] == b[j]:
return solve(i + 1, j + 1)
return 1 + min(
solve(i + 1, j),
solve(i, j + 1),
solve(i + 1, j + 1)
)
return solve(0, 0)Bottom-Up
def edit_distance(a, b):
m = len(a)
n = len(b)
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 a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
)
return dp[m][n]6. Pattern 5 — Grid DP
Recognition
Look for:
- matrix/grid
- move right/down
- number of paths
- minimum cost
- maximum reward
State:
(row, column)Problem 20: Unique Paths
Recursive
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)Memoized
from functools import lru_cache
def uniquePaths(m, n):
@lru_cache(None)
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)Bottom-Up
def uniquePaths(m, n):
dp = [[1] * n for _ in range(m)]
for r in range(1, m):
for c in range(1, n):
dp[r][c] = (
dp[r - 1][c]
+ dp[r][c - 1]
)
return dp[m - 1][n - 1]Problem 21: Unique Paths II
Blocked cells.
def uniquePathsWithObstacles(grid):
m = len(grid)
n = len(grid[0])
dp = [[0] * n for _ in range(m)]
if grid[0][0] == 1:
return 0
dp[0][0] = 1
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
dp[r][c] = 0
continue
if r > 0:
dp[r][c] += dp[r - 1][c]
if c > 0:
dp[r][c] += dp[r][c - 1]
return dp[-1][-1]Problem 22: Minimum Path Sum
Recursive
def minPathSum(grid):
m = len(grid)
n = len(grid[0])
def solve(r, c):
if r == m - 1 and c == n - 1:
return grid[r][c]
if r >= m or c >= n:
return float('inf')
return grid[r][c] + min(
solve(r + 1, c),
solve(r, c + 1)
)
return solve(0, 0)Memoized
from functools import lru_cache
def minPathSum(grid):
m = len(grid)
n = len(grid[0])
@lru_cache(None)
def solve(r, c):
if r == m - 1 and c == n - 1:
return grid[r][c]
if r >= m or c >= n:
return float('inf')
return grid[r][c] + min(
solve(r + 1, c),
solve(r, c + 1)
)
return solve(0, 0)Bottom-Up
def minPathSum(grid):
m = len(grid)
n = len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for r in range(m):
for c in range(n):
if r == 0 and c == 0:
continue
top = (
dp[r - 1][c]
if r > 0
else float('inf')
)
left = (
dp[r][c - 1]
if c > 0
else float('inf')
)
dp[r][c] = (
grid[r][c]
+ min(top, left)
)
return dp[-1][-1]7. Pattern 6 — Longest Increasing Subsequence
Recognition
Look for:
Longest subsequence satisfying an ordering condition.
Typical state:
dp[i]
=
LIS ending at iProblem 23: Longest Increasing Subsequence
A clean recursive formulation is:
def lengthOfLIS(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)The state is:
i + previous indexMemoized:
from functools import lru_cache
def lengthOfLIS(nums):
@lru_cache(None)
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)For the standard bottom-up O(N²) DP:
def lengthOfLIS(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, default=0)8. Pattern 7 — State Machine DP
Recognition
Your state contains:
position/day
+
current statusCommon examples:
Buy / Sell Stock
Cooldown
Transaction Fee
Limited TransactionsProblem 24: Best Time to Buy and Sell Stock II
State:
i
holdingRecursive
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, False)
)
return max(
skip,
sell
)
buy = (
-prices[i]
+ solve(i + 1, True)
)
return max(
skip,
buy
)
return solve(0, False)Memoized
from functools import lru_cache
def maxProfit(prices):
@lru_cache(None)
def solve(i, holding):
if i == len(prices):
return 0
skip = solve(
i + 1,
holding
)
if holding:
sell = (
prices[i]
+ solve(i + 1, False)
)
return max(
skip,
sell
)
buy = (
-prices[i]
+ solve(i + 1, True)
)
return max(
skip,
buy
)
return solve(0, False)Bottom-Up
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]Problem 25: Stock With Cooldown
Now the state becomes:
holding
sold
cooldowndef maxProfit(prices):
if not prices:
return 0
hold = -prices[0]
sold = 0
cooldown = 0
for price in prices[1:]:
old_hold = hold
old_sold = sold
old_cooldown = cooldown
hold = max(
old_hold,
old_cooldown - price
)
sold = old_hold + price
cooldown = max(
old_cooldown,
old_sold
)
return max(
sold,
cooldown
)The important lesson is not the code.
It's:
Add the extra condition to the DP state.
9. Pattern 8 — Interval / MCM DP
Recognition
Look for:
solve(i, j)and:
try every split kThe structure is:
[i ---------------- j]
↓
try every k
[i ---- k] [k+1 ---- j]Common problems:
Matrix Chain Multiplication
Palindrome Partitioning
Burst Balloons
Boolean ParenthesizationProblem 26: Matrix Chain Multiplication
Recursive
def matrix_chain(arr):
def solve(i, j):
if i >= j:
return 0
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
)
return answer
return solve(
1,
len(arr) - 1
)Memoized
from functools import lru_cache
def matrix_chain(arr):
@lru_cache(None)
def solve(i, j):
if i >= j:
return 0
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
)
return answer
return solve(
1,
len(arr) - 1
)Bottom-Up
Here the recursion depends on smaller intervals.
Therefore:
small interval
↓
larger intervaldef matrix_chain(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]Problem 27: Burst Balloons
The trick is to choose the last balloon to burst in an interval.
def maxCoins(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [
[0] * n
for _ in range(n)
]
for length in range(2, n):
for left in range(
0,
n - length
):
right = left + length
for k in range(
left + 1,
right
):
coins = (
nums[left]
* nums[k]
* nums[right]
+ dp[left][k]
+ dp[k][right]
)
dp[left][right] = max(
dp[left][right],
coins
)
return dp[0][n - 1]This is interval DP because:
left
right
split kdefine the state.
10. Pattern 9 — Tree DP
Recognition
Look for:
Tree
+
answer depends on childrenTypical flow:
Solve left
Solve right
↓
Combine
↓
Return information to parentProblem 28: Diameter of Binary Tree
For every node:
left height
right heightPath through node:
left + rightHeight returned:
1 + max(left, right)def diameterOfBinaryTree(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 answerThis is naturally recursive, so forcing a separate DP array would make the solution worse.
Problem 29: Maximum Path Sum
def maxPathSum(root):
answer = float('-inf')
def solve(node):
nonlocal answer
if not node:
return 0
left = max(
0,
solve(node.left)
)
right = max(
0,
solve(node.right)
)
answer = max(
answer,
node.val + left + right
)
return node.val + max(
left,
right
)
solve(root)
return answerProblem 30: House Robber III
At every node:
Rob node
OR
Skip nodeBut if we rob the node, we cannot rob its children.
The state is naturally:
(node, robbed/skipped)def rob(root):
def solve(node):
if not node:
return (0, 0)
left_rob, left_skip = solve(
node.left
)
right_rob, right_skip = solve(
node.right
)
rob_current = (
node.val
+ left_skip
+ right_skip
)
skip_current = (
max(left_rob, left_skip)
+ max(right_rob, right_skip)
)
return (
rob_current,
skip_current
)
return max(solve(root))This is a good example where the recursive return value itself acts as the DP state.
11. Pattern 10 — DAG / Graph DP
Recognition
Look for:
Directed graph
+
No cycles
+
Answer depends on previous nodesA DAG gives us a dependency order.
Typical problems:
Longest Path in DAG
Number of Paths
Minimum Cost PathProblem 31: Longest Path in DAG
from collections import deque
def longest_path(n, edges):
graph = [
[]
for _ in range(n)
]
indegree = [0] * n
for u, v, weight in edges:
graph[u].append(
(v, weight)
)
indegree[v] += 1
queue = deque(
i
for i in range(n)
if indegree[i] == 0
)
dp = [0] * n
while queue:
u = queue.popleft()
for v, weight in graph[u]:
dp[v] = max(
dp[v],
dp[u] + weight
)
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return max(dp)Here the topological ordering replaces the recursion order.
12. Pattern 11 — Bitmask DP
Recognition
Think:
"I need to remember which elements have already been used."
For small N, represent the used elements with a bitmask.
Example:
10101
Element 0 → used
Element 1 → not used
Element 2 → used
Element 3 → not used
Element 4 → usedTypical state:
dp[mask][current]Problem 32: Traveling Salesman
State:
mask
+
current citydef tsp(dist):
n = len(dist)
INF = float('inf')
dp = [
[INF] * n
for _ in range(1 << n)
]
dp[1][0] = 0
for mask in range(1 << n):
for city in range(n):
if not (mask & (1 << city)):
continue
if dp[mask][city] == INF:
continue
for nxt in range(n):
if mask & (1 << nxt):
continue
new_mask = (
mask
| (1 << nxt)
)
dp[new_mask][nxt] = min(
dp[new_mask][nxt],
dp[mask][city]
+ dist[city][nxt]
)
full = (1 << n) - 1
return min(
dp[full][city]
+ dist[city][0]
for city in range(n)
)Complexity:
Time: O(2^N × N²)
Space: O(2^N × N)13. Pattern 12 — Digit DP
This is an advanced pattern.
Recognition
Usually:
Count numbers from 0 to N
+
Digit-related restrictionTypical state:
position
+
tight
+
additional stateFor example:
dp(position, sum, tight)Problem 33: Count Numbers With a Given Digit Sum
from functools import lru_cache
def count_digit_sum(N, target):
digits = list(
map(int, str(N))
)
@lru_cache(None)
def solve(
pos,
current_sum,
tight
):
if current_sum > target:
return 0
if pos == len(digits):
return int(
current_sum == target
)
limit = (
digits[pos]
if tight
else 9
)
answer = 0
for digit in range(
limit + 1
):
answer += solve(
pos + 1,
current_sum + digit,
tight
and digit == limit
)
return answer
return solve(
0,
0,
True
)Digit DP is generally something to learn after the core patterns are comfortable.
14. Pattern 13 — Partition / String DP
Some problems don't fit neatly into LCS or MCM but involve breaking a string into valid pieces.
A common state is:
dp[i]
=
can we solve the prefix ending at i?Problem 34: Word Break
Given a dictionary, determine whether the string can be segmented.
Example:
leetcode
"leet" + "code"Recursive
def wordBreak(s, wordDict):
words = set(wordDict)
def solve(i):
if i == len(s):
return True
for j in range(
i + 1,
len(s) + 1
):
if (
s[i:j] in words
and solve(j)
):
return True
return False
return solve(0)Memoized
from functools import lru_cache
def wordBreak(s, wordDict):
words = set(wordDict)
@lru_cache(None)
def solve(i):
if i == len(s):
return True
for j in range(
i + 1,
len(s) + 1
):
if (
s[i:j] in words
and solve(j)
):
return True
return False
return solve(0)Bottom-Up
def wordBreak(s, wordDict):
words = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(
1,
len(s) + 1
):
for j in range(i):
if (
dp[j]
and s[j:i] in words
):
dp[i] = True
break
return dp[-1]15. The Interview DP Problem Map
You don't need to memorize hundreds of DP problems.
Start with these.
1D DP
1. Climbing Stairs
2. Min Cost Climbing Stairs
3. House Robber
4. House Robber II
5. Decode Ways
6. Word Break0/1 Knapsack
7. 0/1 Knapsack
8. Subset Sum
9. Equal Sum Partition
10. Count Subsets
11. Minimum Subset Sum Difference
12. Target SumUnbounded Knapsack
13. Coin Change
14. Coin Change II
15. Rod CuttingLCS / String DP
16. Longest Common Subsequence
17. Longest Common Substring
18. Edit Distance
19. Shortest Common Supersequence
20. Longest Palindromic Subsequence
21. Minimum Insertions to Palindrome
22. Minimum Deletions to PalindromeGrid DP
23. Unique Paths
24. Unique Paths II
25. Minimum Path SumLIS
26. Longest Increasing Subsequence
27. Maximum Length Chain
28. Russian Doll EnvelopesState Machine DP
29. Stock II
30. Stock With Cooldown
31. Stock With Transaction Fee
32. Stock With K TransactionsInterval DP
33. Matrix Chain Multiplication
34. Palindrome Partitioning
35. Burst Balloons
36. Boolean ParenthesizationTree DP
37. Binary Tree Diameter
38. Maximum Path Sum
39. House Robber III
40. Binary Tree CamerasGraph / DAG DP
41. Longest Path in DAG
42. Number of Paths in DAG
43. Minimum Cost Path in DAGBitmask DP
44. Traveling Salesman
45. Assignment Problem
46. Visit All NodesDigit DP
47. Count Numbers With Digit Sum
48. Count Numbers Without Repeated Digits
49. Count Numbers Matching Digit Constraints16. The DP Recognition Cheat Sheet
When you see a new problem, don't immediately search for a formula.
Ask:
1. What are my choices?
2. What information defines the remaining problem?
3. Can I write solve(state)?
4. Does the same state appear repeatedly?
5. What does solve(state) return?Then classify it.
DP
│
┌─────────────┼─────────────┐
│ │ │
Sequence Choices Structure
│ │ │
↓ ↓ ↓
1D DP Take / Skip Grid
│ │ Tree
│ ├── 0/1 DAG
│ └── Unbounded
│
├── LIS
└── String
│
└── LCSFor more complex states:
Buy / Sell / Hold
→ State Machine DP
[i, j] + split k
→ Interval DP
Used elements
→ Bitmask DP
Digits + range
→ Digit DP17. The Most Important Transformation
This is what you should practice repeatedly.
Start with:
def solve(i, state):Understand the choices.
For example:
take = ...
skip = ...
return max(take, skip)Then memoize:
@lru_cache(None)
def solve(i, state):Then convert the state:
solve(i, state)
↓
dp[i][state]Then look at the dependencies:
dp[i][state]
↓
dp[next_i][next_state]Those dependencies determine:
- table dimensions
- iteration order
- initialization
- space optimization
18. The DP Learning Order
If you're preparing for interviews, learn these in this order.
Level 1 — Foundation
1. Climbing Stairs
2. House Robber
3. Decode WaysLearn:
state
choices
recursion
memoization
1D DPLevel 2 — Knapsack
4. Subset Sum
5. Partition
6. Target Sum
7. Coin ChangeLearn:
take / skip
0/1 vs unbounded
count vs boolean vs optimizationLevel 3 — Two-Dimensional DP
8. LCS
9. Edit Distance
10. Unique Paths
11. Minimum Path SumLearn:
dp[i][j]Level 4 — Advanced Structures
12. LIS
13. Stock DP
14. Interval DP
15. Tree DPLevel 5 — Advanced Interview / Hard
16. DAG DP
17. Bitmask DP
18. Digit DPFinal Mental Model
Don't memorize:
House Robber formula
Knapsack formula
LCS formula
Coin Change formulaInstead memorize the process:
NEW PROBLEM
│
↓
Find choices
│
↓
Define recursive
state
│
↓
Recursion
│
↓
Repeated states?
/ \
No Yes
│ │
│ Memoization
│ │
└──────┬───────┘
↓
DP state
↓
Tabulation
↓
Can space be reduced?
│
↓
Optimized DPThe most important rule is:
Don't start with the DP array. Start with the recursive decision process.
Once you can write the correct recursion, memoization is usually just caching, and tabulation is usually just changing the order in which those same states are evaluated.
That is the core skill that makes DP problems predictable rather than mysterious.