lru_cache converts top-down recursion to DP. Eliminates manual memo dict boilerplate.
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(n):
...Bottom-up 1D DP builds solutions iteratively. Avoids recursion depth limits.
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = ... # recurrence2D DP grid handles two-dimensional state. Foundation for LCS, edit distance, and grid paths.
dp = [[0] * (m + 1) for _ in range(n + 1)]Fibonacci DP is the simplest recurrence. Same pattern as climbing stairs.
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]Unbounded knapsack DP: iterate coins outer, amounts inner. Classic DP problem.
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)Subset backtracking explores include/exclude decisions. Foundation for power set and combination sum.
def bt(i, cur):
res.append(cur[:])
for j in range(i, n):
cur.append(a[j])
bt(j + 1, cur)
cur.pop()
bt(0, [])Permutation backtracking generates all orderings. Used in arrangement and scheduling problems.
def bt(cur):
if len(cur) == n:
res.append(cur[:])
return
for x in a:
if x not in cur:
cur.append(x)
bt(cur)
cur.pop()
bt([])Combination backtracking selects k items from n. Avoids duplicates by advancing the start index.
def bt(start, cur):
if len(cur) == k:
res.append(cur[:])
return
for i in range(start, n):
cur.append(a[i])
bt(i + 1, cur)
cur.pop()
bt(0, [])1D DP accumulation for grid paths. Space-optimized from 2D.
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]Longest Common Subsequence is a classic 2D DP. Foundation for diff algorithms.
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])Edit distance uses three operations: insert, delete, replace. Each maps to a DP neighbor.
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])Counting coin combinations iterates coins outer to avoid permutation double-counting.
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for a in range(c, amount + 1):
dp[a] += dp[a - c]Transform target sum into a subset-sum problem via (total + target) / 2.
total = sum(nums)
if (total + target) % 2: return 0
s = (total + target) // 2
dp = [0] * (s + 1)
dp[0] = 1
for n in nums:
for j in range(s, n-1, -1):
dp[j] += dp[j - n]2D DP checks if characters from s1 and s2 interleave to form s3.
dp[0][0] = True
for i in range(m+1):
for j in range(n+1):
if i and s1[i-1] == s3[i+j-1]: dp[i][j] |= dp[i-1][j]
if j and s2[j-1] == s3[i+j-1]: dp[i][j] |= dp[i][j-1]Track open/close counts. Only add close paren when close < open.
def bt(o, c, cur):
if len(cur) == 2*n: res.append(cur); return
if o < n: bt(o+1, c, cur+'(')
if c < o: bt(o, c+1, cur+')')Before writing any DP code, verify both conditions: overlapping subproblems AND optimal substructure. If only one holds, DP won't help.
RECOGNIZING A DP PROBLEM — CHECKLIST
─────────────────────────────────────
1. OVERLAPPING SUBPROBLEMS?
→ Same function called with same args multiple times
→ Draw the recursion tree: do branches repeat?
2. OPTIMAL SUBSTRUCTURE?
→ Optimal solution built from optimal sub-solutions
→ "Best of X" = best(sub1) + best(sub2)?
3. CLASSIC SIGNALS in problem statement:
□ "minimum cost / maximum profit"
□ "number of ways to..."
□ "can you reach / is it possible"
□ "longest / shortest subsequence"
□ "partition into groups optimally"
4. NOT DP if:
× Need the actual path, not just cost → maybe BFS
× Greedy choice property holds → greedy
× No overlapping subproblems → plain recursionTop-down is easier to write and debug. Bottom-up avoids stack overflow and is faster. Know both, convert between them.
TOP-DOWN (memoization) BOTTOM-UP (tabulation)
───────────────────── ──────────────────────
+ Natural recursive thinking + No recursion stack limit
+ Only computes needed states + Often cache-friendly
- Python recursion limit - Must fill entire table
- Stack overhead - Must figure iteration order
CONVERSION STEPS:
Top-down → Bottom-up:
1. Identify base cases → fill dp table edges
2. Reverse recursion → forward iteration
3. memo dict → dp array
Bottom-up → Space-optimized:
1. Check: does dp[i] only depend on dp[i-1]?
2. Yes → keep only prev row/value
3. Two rows → rolling array
Rule: start top-down for correctness,
convert to bottom-up if perf matters.Defining the state is the hardest part of DP. Get this right and the recurrence writes itself.
DP STATE DEFINITION — "WHAT CHANGES?"
──────────────────────────────────────
Ask: what variables change between subproblems?
COMMON STATE PATTERNS:
1D: dp[i] = answer for first i items
→ climbing stairs, house robber, word break
2D: dp[i][j] = answer for items i..j (intervals)
→ palindrome, matrix chain, burst balloons
OR dp[i][j] = answer using i items with capacity j
→ knapsack, edit distance, LCS
State machine: dp[i][state]
→ stock buy/sell (hold/sold/rest)
→ house robber circular
Bitmask: dp[mask] = answer for subset represented by mask
→ TSP, partition to K subsets
CHECKLIST:
□ What is the "answer" stored in dp[...]?
□ What are the dimensions? (index, capacity, state)
□ What are the transitions? dp[i] = f(dp[i-1], ...)
□ What are the base cases?Most 2D DP can be reduced to 1D. Most 1D DP can be reduced to a few variables. Always check dependencies.
SPACE OPTIMIZATION PATTERNS
────────────────────────────
# 2D → 1D (when row i only depends on row i-1):
# BEFORE: O(n*m) space
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = dp[i-1][j-1] + 1 # example
# AFTER: O(m) space — two rows
prev, curr = [0]*(m+1), [0]*(m+1)
for i in range(1, n+1):
for j in range(1, m+1):
curr[j] = prev[j-1] + 1
prev, curr = curr, [0]*(m+1)
# 1D → O(1) (when dp[i] only needs dp[i-1], dp[i-2]):
# BEFORE:
dp = [0] * n
# AFTER:
a, b = base0, base1
for i in range(2, n):
a, b = b, f(a, b)
KEY: iterate inner loop BACKWARDS for 0/1 knapsack
to avoid using updated values.Counting how many variables change between subproblems immediately tells you the DP table dimensionality.
1D vs 2D DP — DECISION TREE
────────────────────────────
Q: How many things change between subproblems?
ONE THING changes → 1D dp[i]
"first i elements" or "up to value i"
Examples: climbing stairs, house robber,
word break, decode ways, coin change
TWO THINGS change → 2D dp[i][j]
Patterns:
┌─ Two sequences → dp[i][j] = first i of seq1, j of seq2
│ LCS, edit distance, regex matching
├─ Interval → dp[i][j] = substring s[i..j]
│ Palindrome, matrix chain, burst balloons
├─ Index + capacity → dp[i][w] = first i items, weight w
│ Knapsack, subset sum
└─ Index + state → dp[i][s] = at position i in state s
Stock problems, paint house
SHORTCUT: if problem has two input arrays/strings → 2D
if problem says "capacity" or "limit" → 2DThe inner loop goes BACKWARDS to prevent reusing item i. Forward loop = unbounded knapsack.
def knapsack(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1): # backwards!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]dp[i] = length of longest increasing subsequence ending at index i. Classic O(n²) DP.
def lengthOfLIS(nums):
n = len(nums)
dp = [1] * n # each element is a subsequence of length 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Patience sorting: maintain smallest possible tails. bisect_left finds where to place each element.
import bisect
def lengthOfLIS(nums):
tails = [] # tails[i] = smallest tail of IS of length i+1
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)Expand around center: try each index as center for odd and even palindromes. O(n²) time, O(1) space.
def longestPalindrome(s):
res = ""
for i in range(len(s)):
# odd length
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1; r += 1
# even length
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1; r += 1
return res2D interval DP. Iterate i from bottom-up so dp[i+1] is already computed. Equivalent to LCS(s, reverse(s)).
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]dp[i] = can s[:i] be segmented? Try every split point j where dp[j] is True and s[j:i] is a word.
def wordBreak(s, wordDict):
words = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]Like climbing stairs but with validity checks. Single digit (1-9) adds dp[i-1], two digits (10-26) adds dp[i-2].
def numDecodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
if s[i-1] != '0':
dp[i] += dp[i-1]
two = int(s[i-2:i])
if 10 <= two <= 26:
dp[i] += dp[i-2]
return dp[n]At each house: rob it (prev2 + current) or skip it (prev1). Classic two-variable DP.
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = 0, 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1Circular constraint: first and last are adjacent. Solve twice: once excluding first, once excluding last.
def rob(nums):
if len(nums) == 1: return nums[0]
def rob_linear(arr):
prev2, prev1 = 0, 0
for x in arr:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
return max(rob_linear(nums[1:]), # skip first
rob_linear(nums[:-1])) # skip lastdp[i] = cost[i] + min(dp[i-1], dp[i-2]). Optimized to two variables. Final answer is min of last two.
def minCostClimbingStairs(cost):
a, b = cost[0], cost[1]
for i in range(2, len(cost)):
a, b = b, cost[i] + min(a, b)
return min(a, b)Three-state machine: hold → sell → rest → buy. After selling, must rest one day before buying.
def maxProfit(prices):
hold = -prices[0] # holding stock
sold = 0 # just sold (cooldown next)
rest = 0 # not holding, free to buy
for p in prices[1:]:
hold, sold, rest = (
max(hold, rest - p), # keep or buy
hold + p, # sell
max(rest, sold), # stay or come off cooldown
)
return max(sold, rest)Two-state DP: cash (free to buy) and hold (free to sell). Fee paid on sell. No cooldown needed.
def maxProfit(prices, fee):
cash = 0 # not holding
hold = -prices[0] # holding
for p in prices[1:]:
cash = max(cash, hold + p - fee)
hold = max(hold, cash - p)
return cashTrack both max and min product (negative * negative = positive). Swap on negative number.
def maxProduct(nums):
res = mx = mn = nums[0]
for x in nums[1:]:
if x < 0:
mx, mn = mn, mx # swap before multiply
mx = max(x, mx * x)
mn = min(x, mn * x)
res = max(res, mx)
return resAt each element: extend current subarray or start fresh. The simplest DP pattern — must be instant.
def maxSubArray(nums):
cur = res = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
res = max(res, cur)
return resClassic 2D grid DP. Each cell = its value + min(top, left). In-place to avoid extra space.
def minPathSum(grid):
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
elif i == 0: grid[i][j] += grid[i][j-1]
elif j == 0: grid[i][j] += grid[i-1][j]
else: grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]Bottom-up on triangle: each cell picks the smaller child. 1D array suffices since we overwrite left to right.
def minimumTotal(triangle):
dp = triangle[-1][:] # start from bottom row
for i in range(len(triangle) - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
return dp[0]Reduces to 0/1 knapsack: can we pick a subset summing to total/2? Backwards loop prevents item reuse.
def canPartition(nums):
total = sum(nums)
if total % 2: return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for x in nums:
for j in range(target, x - 1, -1): # backwards!
dp[j] = dp[j] or dp[j - x]
return dp[target]Two-phase DP: first build O(n²) palindrome lookup, then find min cuts. Common two-table pattern.
def minCut(s):
n = len(s)
# precompute palindrome table
is_pal = [[False]*n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i < 2 or is_pal[i+1][j-1]):
is_pal[i][j] = True
# dp[i] = min cuts for s[0..i]
dp = list(range(n)) # worst case: cut before every char
for i in range(1, n):
if is_pal[0][i]:
dp[i] = 0; continue
for j in range(1, i+1):
if is_pal[j][i]:
dp[i] = min(dp[i], dp[j-1] + 1)
return dp[n-1]Interval DP: dp[l][r] = max coins from bursting all balloons between l and r. k is the LAST one burst.
def maxCoins(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0]*n for _ in range(n)]
for length in range(2, n): # gap between l and r
for l in range(0, n - length):
r = l + length
for k in range(l+1, r): # last balloon to burst
dp[l][r] = max(dp[l][r],
dp[l][k] + dp[k][r] + nums[l]*nums[k]*nums[r])
return dp[0][n-1]Interval DP template: enumerate gap size → left endpoint → split point. O(n³). Same structure as burst balloons.
def matrixChainOrder(dims):
# dims[i-1] x dims[i] = matrix i dimensions
n = len(dims) - 1
dp = [[0]*n for _ in range(n)]
for length in range(2, n + 1):
for i in range(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]
+ dims[i]*dims[k+1]*dims[j+1])
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]Bitmask DP: represent subset as integer, each bit = included/excluded. O(2^n * n). For n ≤ 20.
def bitmaskDP(n, cost):
# dp[mask] = best answer using subset 'mask'
dp = [float('inf')] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == float('inf'): continue
for i in range(n):
if mask & (1 << i): continue # already used
new_mask = mask | (1 << i)
bits = bin(mask).count('1') # position = items used so far
dp[new_mask] = min(dp[new_mask],
dp[mask] + cost[bits][i])
return dp[(1 << n) - 1]Digit DP: count numbers up to N with some property. 'tight' tracks if we're still bounded by N's digits.
from functools import lru_cache
def countDigitDP(num):
digits = list(map(int, str(num)))
@lru_cache(maxsize=None)
def dp(pos, tight, started):
if pos == len(digits):
return 1 if started else 0
limit = digits[pos] if tight else 9
res = 0
for d in range(0, limit + 1):
res += dp(pos + 1,
tight and d == limit,
started or d > 0)
return res
return dp(0, True, False)2D DP matching string vs pattern. '*' means zero or more of preceding element. '.' matches any single char.
def isMatch(s, p):
m, n = len(s), len(p)
dp = [[False]*(n+1) for _ in range(m+1)]
dp[0][0] = True
for j in range(1, n+1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2] # x* matches empty
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] == '*':
dp[i][j] = dp[i][j-2] # zero occurrences
if p[j-2] == '.' or p[j-2] == s[i-1]:
dp[i][j] |= dp[i-1][j] # one+ occurrences
elif p[j-1] == '.' or p[j-1] == s[i-1]:
dp[i][j] = dp[i-1][j-1]
return dp[m][n]'*' matches any sequence (dp[i-1][j] = consume char, dp[i][j-1] = empty match). '?' matches any single char.
def isMatch(s, p):
m, n = len(s), len(p)
dp = [[False]*(n+1) for _ in range(m+1)]
dp[0][0] = True
for j in range(1, n+1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-1]
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1]
elif p[j-1] == '?' or p[j-1] == s[i-1]:
dp[i][j] = dp[i-1][j-1]
return dp[m][n]dp[i][j] = side length of largest square with bottom-right at (i,j). min of three neighbors + 1.
def maximalSquare(matrix):
m, n = len(matrix), len(matrix[0])
dp = [[0]*n for _ in range(m)]
res = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1],
dp[i-1][j-1]) + 1
res = max(res, dp[i][j])
return res * resEvery recursion can be converted to iteration with an explicit stack. Tail recursion converts to a simple loop.
RECURSION → ITERATION CONVERSION
─────────────────────────────────
STEP 1: Identify what the call stack stores
→ Parameters + local variables + return point
STEP 2: Replace call stack with explicit stack
stack = [(initial_params)]
while stack:
params = stack.pop()
# ... process ...
stack.append(next_params) # instead of recursive call
STEP 3: Handle return values
→ Use a result variable or secondary stack
TAIL RECURSION (easy):
# Recursive:
def f(n, acc=0):
if n == 0: return acc
return f(n-1, acc+n)
# Iterative:
acc = 0
while n > 0: acc += n; n -= 1
TREE RECURSION (use stack):
# Recursive: # Iterative:
def dfs(node): stack = [root]
process(node) while stack:
dfs(node.left) node = stack.pop()
dfs(node.right) process(node)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)Greedy never backtracks. DP explores all options. If you can't prove greedy works with an exchange argument, use DP.
GREEDY vs DP — KEY DIFFERENCE
─────────────────────────────
GREEDY: make locally optimal choice at each step
→ Never reconsider previous choices
→ No overlapping subproblems needed
→ O(n) or O(n log n) typically
DP: consider ALL choices, pick globally optimal
→ May revisit states through memoization
→ Requires overlapping subproblems
→ O(n²) or O(n*W) typically
HOW TO TELL:
□ Can you prove greedy works? (exchange argument)
□ Does local best = global best? → greedy
□ Counterexample found? → need DP
CLASSIC GREEDY:
Activity selection, interval scheduling, Huffman,
jump game, gas station, assign cookies
CLASSIC DP:
Knapsack, coin change, LCS, edit distance
TRAP: coin change is DP (greedy fails for [1,3,4] target=6)
but interval scheduling is greedy (sort by end time)