DP Fundamentals
WITHOUT DP — Fibonacci(5) O(2^n) calls
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) ... ... ...
↑ fib(2) computed 3 times, fib(3) computed 2 times
WITH DP — Fibonacci(5) O(n) calls
fib(1) → fib(2) → fib(3) → fib(4) → fib(5)
Each subproblem solved exactly once, result cached
| When to Use DP |
|---|
| Overlapping Subproblems | Same subproblem solved multiple times |
| Optimal Substructure | Optimal solution built from optimal sub-solutions |
| Technique | Key Idea |
|---|
| DP | Overlapping subproblems + optimal substructure |
| Greedy | Local best choice at each step, no backtracking |
| Divide & Conquer | Non-overlapping subproblems (merge sort, quick sort) |
| Backtracking | Try all choices, prune invalid branches |
- Smart recursion = recursion + caching
- Solves each subproblem exactly once
- Transforms exponential time to polynomial time
// Top-Down: Memoization
fun fib(n: Int, memo: MutableMap<Int, Long> = mutableMapOf()): Long {
if (n <= 1) return n.toLong()
memo[n]?.let { return it }
val result = fib(n - 1, memo) + fib(n - 2, memo)
memo[n] = result
return result
}
// Bottom-Up: Tabulation
fun fib(n: Int): Long {
if (n <= 1) return n.toLong()
val dp = LongArray(n + 1)
dp[0] = 0; dp[1] = 1
for (i in 2..n) dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
}
| Aspect | Top-Down (Memo) | Bottom-Up (Tab) |
|---|
| Implementation | Recursive + cache | Iterative + table |
| Direction | Big → small | Small → big |
| Subproblems solved | Only needed ones | All subproblems |
| Stack overflow risk | Yes (deep recursion) | No |
| Space optimization | Hard | Easy (rolling vars) |
| When to prefer | Complex states, sparse | Dense, need speed |
DP Workflow
Brute Force → Add Memo → Convert to Bottom-Up → Space Optimize
(exponential) (polynomial) (no stack overflow) (minimal memory)
- Start with memoization for correctness
- Convert to bottom-up for performance
- Space optimize as the final step
5 Steps to Solve Any DP Problem
1. Define state dp[i] = answer for subproblem i
2. Write recurrence dp[i] = f(dp[i-1], dp[i-2], ...)
3. Base cases dp[0] = ..., dp[1] = ...
4. Fill order left→right, bottom→top, by length, etc.
5. Extract answer dp[n], dp[m][n], max(dp), etc.
// Example: Min Cost Climbing Stairs
fun minCostClimbingStairs(cost: IntArray): Int {
// 1. State: dp[i] = min cost to reach step i
// 2. Recurrence: dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
// 3. Base cases: dp[0]=0, dp[1]=0 (start from 0 or 1)
var prev2 = 0; var prev1 = 0
for (i in 2..cost.size) { // 4. Fill left→right
val curr = minOf(prev1 + cost[i - 1], prev2 + cost[i - 2])
prev2 = prev1; prev1 = curr
}
return prev1 // 5. Answer = dp[n]
}
- Every DP problem follows these 5 steps
- State definition is the hardest part — spend the most time here
// Rolling variables: 1D table → O(1)
fun fibOptimized(n: Int): Long {
if (n <= 1) return n.toLong()
var prev2 = 0L; var prev1 = 1L
for (i in 2..n) {
val curr = prev1 + prev2
prev2 = prev1; prev1 = curr
}
return prev1
}
// Rolling row: 2D table → 1D
fun uniquePathsOptimized(m: Int, n: Int): Int {
val dp = IntArray(n) { 1 }
for (i in 1 until m)
for (j in 1 until n)
dp[j] += dp[j - 1]
return dp[n - 1]
}
- Optimize only after correctness is verified
- Check dependency direction — can you discard old rows/values?
1D DP Patterns
Kadane's Algorithm → max subarray with visualizer (see Arrays page) |
Expression Evaluation → stack-based calculator (see Stacks page)
// Fibonacci — space optimized
fun fib(n: Int): Int {
if (n <= 1) return n
var prev2 = 0; var prev1 = 1
for (i in 2..n) {
val curr = prev1 + prev2
prev2 = prev1; prev1 = curr
}
return prev1
}
// Climbing Stairs
fun climbStairs(n: Int): Int {
if (n <= 2) return n
var prev2 = 1; var prev1 = 2
for (i in 3..n) {
val curr = prev1 + prev2
prev2 = prev1; prev1 = curr
}
return prev1
}
// Generalized: up to k steps
fun climbStairsK(n: Int, k: Int): Int {
val dp = IntArray(n + 1)
dp[0] = 1
for (i in 1..n)
for (j in 1..minOf(i, k))
dp[i] += dp[i - j]
return dp[n]
}
When to Use
fibonacci (tabulation)Why: dp[n] = dp[n-1] + dp[n-2]. The canonical DP example. Memo turns O(2^n) → O(n). Rolling vars → O(1) space.
climbing stairsWhy: Identical to fibonacci: ways to reach step n = ways to reach n-1 + ways to reach n-2. dp[i] = dp[i-1] + dp[i-2].
min cost climbing stairsWhy: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Same recurrence but with a cost layer on top.
tribonacci / n-step stairsWhy: Generalize: dp[i] = sum of previous k values. Inner loop over step sizes.
- dp[i] = dp[i-1] + dp[i-2] — the fundamental recurrence
- Generalize to k steps with inner loop over step sizes
- O(1) space with rolling variables
▶ Visualize
// Linear House Robber
fun rob(nums: IntArray): Int {
var prev2 = 0; var prev1 = 0
for (num in nums) {
val curr = maxOf(prev1, prev2 + num)
prev2 = prev1; prev1 = curr
}
return prev1
}
// Circular House Robber
fun robCircular(nums: IntArray): Int {
if (nums.size == 1) return nums[0]
fun robRange(lo: Int, hi: Int): Int {
var prev2 = 0; var prev1 = 0
for (i in lo..hi) {
val curr = maxOf(prev1, prev2 + nums[i])
prev2 = prev1; prev1 = curr
}
return prev1
}
return maxOf(robRange(0, nums.size - 2), robRange(1, nums.size - 1))
}
When to Use
house robber (linear)Why: Can't pick adjacent elements. dp[i] = max(skip, take). Classic "include/exclude with adjacency constraint."
house robber ii (circular)Why: First and last are adjacent. Solve twice: exclude first OR exclude last. Max of both.
house robber iii (tree)Why: DP on tree: return (rob, skip) pair per node. Rob = val + skip(children). Skip = max(rob, skip) per child.
delete and earnWhy: Reduce to house robber: count[v] × v = "value at house v". Can't pick adjacent values → same recurrence.
max alternating subsequence sumWhy: Same take/skip pattern with constraint. dp tracks best ending with include vs exclude.
- dp[i] = max(skip=dp[i-1], rob=dp[i-2]+nums[i])
- Circular version splits into two linear problems: exclude first or last
▶ Visualize
// Minimum coins to make amount
fun coinChange(coins: IntArray, amount: Int): Int {
val dp = IntArray(amount + 1) { amount + 1 }
dp[0] = 0
for (a in 1..amount)
for (coin in coins)
if (coin <= a)
dp[a] = minOf(dp[a], dp[a - coin] + 1)
return if (dp[amount] > amount) -1 else dp[amount]
}
// Count combinations (coins outer → combos)
fun coinChangeWays(coins: IntArray, amount: Int): Int {
val dp = IntArray(amount + 1)
dp[0] = 1
for (coin in coins) // coins outer = combinations
for (a in coin..amount)
dp[a] += dp[a - coin]
return dp[amount]
}
When to Use
coin change (min coins)Why: dp[amount] = min over coins of dp[amount - coin] + 1. Unbounded knapsack variant — each coin reusable.
coin change ii (count ways)Why: Coins outer, amounts inner → combinations (order doesn't matter). Amounts outer, coins inner → permutations.
combination sum ivWhy: Count ordered combinations summing to target. Amounts outer loop — treats [1,2] and [2,1] as different.
minimum cost for ticketsWhy: dp[day] = min cost to cover travel through day. Try 1-day, 7-day, 30-day passes at each travel day.
- Min coins: dp[a] = min(dp[a - coin] + 1)
- Count ways: coins outer loop → combinations; amounts outer → permutations
▶ Visualize
// O(n²) DP
fun lengthOfLIS(nums: IntArray): Int {
val dp = IntArray(nums.size) { 1 }
for (i in nums.indices)
for (j in 0 until i)
if (nums[j] < nums[i])
dp[i] = maxOf(dp[i], dp[j] + 1)
return dp.max()
}
// O(n log n) with binary search
fun lengthOfLISBinarySearch(nums: IntArray): Int {
val tails = mutableListOf<Int>()
for (num in nums) {
var lo = 0; var hi = tails.size
while (lo < hi) {
val mid = (lo + hi) / 2
if (tails[mid] < num) lo = mid + 1 else hi = mid
}
if (lo == tails.size) tails.add(num) else tails[lo] = num
}
return tails.size
}
When to Use
lis (o(n²) dp)Why: dp[i] = LIS ending at i. O(n²) DP or O(n log n) with patience sorting (tails + binary search).
number of lisWhy: Track both length and count at each position. When dp[j]+1 == dp[i], add count[j] to count[i].
longest chain of pairsWhy: Sort by second element, then LIS on first elements. Or greedy like activity selection.
russian doll envelopesWhy: Sort by width ascending (height descending for ties), then LIS on heights. 2D LIS reduction.
longest non-decreasing subsequenceWhy: Same as LIS but use ≤ instead of <. Binary search uses upper_bound instead of lower_bound.
- O(n²) checks all j < i where nums[j] < nums[i]
- O(n log n) maintains tails array with binary search replacement
▶ Visualize
// Max subarray sum
fun maxSubArray(nums: IntArray): Int {
var curr = nums[0]; var best = nums[0]
for (i in 1 until nums.size) {
curr = maxOf(nums[i], curr + nums[i])
best = maxOf(best, curr)
}
return best
}
// Max product subarray
fun maxProduct(nums: IntArray): Int {
var maxP = nums[0]; var minP = nums[0]; var best = nums[0]
for (i in 1 until nums.size) {
val candidates = intArrayOf(nums[i], maxP * nums[i], minP * nums[i])
maxP = candidates.max(); minP = candidates.min()
best = maxOf(best, maxP)
}
return best
}
When to Use
maximum subarray sumWhy: Kadane's: dp[i] = max(nums[i], dp[i-1]+nums[i]). Extend current subarray or start fresh. O(n), O(1) space.
maximum product subarrayWhy: Track both max AND min at each position. Negative × negative = positive, so min can become max.
max circular subarray sumWhy: Answer = max(normal Kadane, totalSum - minSubarray). Circular wrap = total minus the minimum contiguous segment.
max sum of non-overlapping subarraysWhy: Kadane left-to-right + Kadane right-to-left. Best split = max(leftMax[i] + rightMax[i+1]).
- dp[i] = max(nums[i], dp[i-1]+nums[i]) — extend or restart
- Product variant needs min tracking because negative × negative = positive
▶ Visualize
// Decode Ways — O(1) space
fun numDecodings(s: String): Int {
if (s[0] == '0') return 0
var prev2 = 1; var prev1 = 1
for (i in 1 until s.length) {
var curr = 0
if (s[i] != '0') curr += prev1
val two = s.substring(i - 1, i + 1).toInt()
if (two in 10..26) curr += prev2
prev2 = prev1; prev1 = curr
}
return prev1
}
// Word Break
fun wordBreak(s: String, wordDict: List<String>): Boolean {
val words = wordDict.toHashSet()
val dp = BooleanArray(s.length + 1)
dp[0] = true
for (i in 1..s.length)
for (j in 0 until i)
if (dp[j] && s.substring(j, i) in words) {
dp[i] = true; break
}
return dp[s.length]
}
When to Use
decode waysWhy: Like climbing stairs but only valid 1-2 digit codes (1-26). dp[i] += dp[i-1] if single valid, += dp[i-2] if double valid.
word breakWhy: dp[i] = can s[0..i-1] be segmented? Check all j: dp[j] && s[j..i] in dict. O(n² × L).
word break ii (all segmentations)Why: Same DP + backtracking to collect all valid segmentations. Memoize to avoid re-exploring.
restore ip addresses (dp)Why: Partition string into 4 valid octets (0-255). DP/backtracking with validity constraints at each split.
- Decode ways is similar to climbing stairs with constraints on valid codes
- Word break checks all prefixes in dictionary at each position
▶ Visualize
// Can Jump — greedy farthest reach
fun canJump(nums: IntArray): Boolean {
var farthest = 0
for (i in nums.indices) {
if (i > farthest) return false
farthest = maxOf(farthest, i + nums[i])
}
return true
}
// Min Jumps — BFS-style levels
fun jump(nums: IntArray): Int {
var jumps = 0; var curEnd = 0; var farthest = 0
for (i in 0 until nums.size - 1) {
farthest = maxOf(farthest, i + nums[i])
if (i == curEnd) { jumps++; curEnd = farthest }
}
return jumps
}
When to Use
can jump (greedy)Why: Greedy: track farthest reachable. If current index > farthest → stuck. O(n), O(1).
min jumps (bfs greedy)Why: BFS-level greedy: each "level" = one jump. Track currentEnd and farthest. Increment jumps when i == currentEnd.
frog jumpWhy: DP with HashSet per stone: track which jump sizes can reach it. For each stone, try k-1, k, k+1.
- Greedy tracks farthest reachable index
- Min jumps uses BFS levels — increment jumps when current level ends
- DP approach is O(n²) — greedy is optimal here
▶ Visualize
fun numSquares(n: Int): Int {
val dp = IntArray(n + 1) { Int.MAX_VALUE }
dp[0] = 0
for (i in 1..n)
var k = 1
while (k * k <= i) {
dp[i] = minOf(dp[i], dp[i - k * k] + 1)
k++
}
return dp[n]
}
When to Use
perfect squaresWhy: dp[n] = min(dp[n-k²]+1). Identical to coin change where "coins" are 1,4,9,16,... O(n√n).
ugly numbersWhy: DP generating sequence: track pointers for ×2, ×3, ×5. Next ugly = min of three candidates.
integer breakWhy: dp[n] = max(j × (n-j), j × dp[n-j]) for all j. Break n into parts that maximize product.
- dp[n] = min(dp[n - k²] + 1) for all valid k
- Same structure as coin change where coins are perfect squares
▶ Visualize
2D DP Patterns
// Unique Paths — space optimized
fun uniquePaths(m: Int, n: Int): Int {
val dp = IntArray(n) { 1 }
for (i in 1 until m)
for (j in 1 until n)
dp[j] += dp[j - 1]
return dp[n - 1]
}
// With Obstacles
fun uniquePathsWithObstacles(grid: Array<IntArray>): Int {
val n = grid[0].size
val dp = IntArray(n)
dp[0] = 1
for (row in grid) {
for (j in 0 until n) {
if (row[j] == 1) dp[j] = 0
else if (j > 0) dp[j] += dp[j - 1]
}
}
return dp[n - 1]
}
// Min Path Sum
fun minPathSum(grid: Array<IntArray>): Int {
val m = grid.size; val n = grid[0].size
for (i in 0 until m)
for (j in 0 until n) {
if (i == 0 && j == 0) continue
val up = if (i > 0) grid[i-1][j] else Int.MAX_VALUE
val left = if (j > 0) grid[i][j-1] else Int.MAX_VALUE
grid[i][j] += minOf(up, left)
}
return grid[m-1][n-1]
}
When to Use
unique pathsWhy: Count paths from top-left to bottom-right (right/down only). dp[i][j] = dp[i-1][j] + dp[i][j-1]. O(m×n), optimizable to O(n).
unique paths with obstaclesWhy: Same recurrence but dp[i][j] = 0 if grid[i][j] is obstacle.
min path sumWhy: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Same grid, minimize instead of count.
triangle minimum path sumWhy: Bottom-up: dp[i][j] += min(dp[i+1][j], dp[i+1][j+1]). Triangular grid DP.
maximal squareWhy: dp[i][j] = min(left, top, diagonal) + 1 if cell is '1'. Track largest square of all 1s.
- dp[i][j] = dp[i-1][j] + dp[i][j-1] for path counting
- Obstacles set dp to 0
- Optimize to single row since each cell depends only on current and previous row
▶ Visualize
// LCS length
fun longestCommonSubsequence(s1: String, s2: String): Int {
val m = s1.length; val n = s2.length
val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 1..m)
for (j in 1..n)
dp[i][j] = if (s1[i-1] == s2[j-1]) dp[i-1][j-1] + 1
else maxOf(dp[i-1][j], dp[i][j-1])
return dp[m][n]
}
// Reconstruct LCS string
fun lcsString(s1: String, s2: String): String {
val m = s1.length; val n = s2.length
val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 1..m)
for (j in 1..n)
dp[i][j] = if (s1[i-1] == s2[j-1]) dp[i-1][j-1] + 1
else maxOf(dp[i-1][j], dp[i][j-1])
val sb = StringBuilder()
var i = m; var j = n
while (i > 0 && j > 0) {
when {
s1[i-1] == s2[j-1] -> { sb.append(s1[i-1]); i--; j-- }
dp[i-1][j] > dp[i][j-1] -> i--
else -> j--
}
}
return sb.reverse().toString()
}
When to Use
lcs lengthWhy: Two strings, find longest shared subsequence. Match → diagonal+1, mismatch → max(skip from either). O(m×n).
shortest common supersequenceWhy: Length = m + n - LCS. Reconstruct by interleaving both strings, sharing LCS characters.
min insertions for palindromeWhy: = n - LPS(s). LPS = LCS(s, reverse(s)). Insert the non-palindromic chars.
diff / patchWhy: LCS of two file versions = unchanged lines. Differences = lines not in LCS.
- Match → dp[i-1][j-1]+1, mismatch → max(dp[i-1][j], dp[i][j-1])
- Reconstruct by backtracking through the table
▶ Visualize
fun minDistance(word1: String, word2: String): Int {
val m = word1.length; val n = word2.length
val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 0..m) dp[i][0] = i
for (j in 0..n) dp[0][j] = j
for (i in 1..m)
for (j in 1..n)
dp[i][j] = if (word1[i-1] == word2[j-1]) dp[i-1][j-1]
else 1 + minOf(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
}
When to Use
edit distanceWhy: Min insert/delete/replace to transform s1→s2. dp[i][j] = cost for s1[0..i-1]↔s2[0..j-1]. O(m×n).
one edit distanceWhy: Simplified: are two strings exactly one edit apart? Compare lengths, scan for the single difference.
min ascii delete sumWhy: Same DP structure but cost = ASCII values of deleted chars instead of count.
distinct subsequencesWhy: Count ways s contains t as subsequence. Match → dp[i-1][j-1]+dp[i-1][j], skip → dp[i-1][j].
spell check suggestionsWhy: Rank dictionary words by edit distance to misspelled word. Edit distance is the core metric.
- Three operations: insert, delete, replace
- Match → dp[i-1][j-1], else → 1 + min(delete, insert, replace)
▶ Visualize
// 1D optimized — RIGHT-TO-LEFT for 0/1
fun knapsack01(weights: IntArray, values: IntArray, W: Int): Int {
val dp = IntArray(W + 1)
for (i in weights.indices)
for (w in W downTo weights[i]) // RIGHT-TO-LEFT!
dp[w] = maxOf(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
}
// 2D version for understanding
fun knapsack01Full(weights: IntArray, values: IntArray, W: Int): Int {
val n = weights.size
val dp = Array(n + 1) { IntArray(W + 1) }
for (i in 1..n)
for (w in 0..W)
dp[i][w] = if (weights[i-1] > w) dp[i-1][w]
else maxOf(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][W]
}
Why Direction Matters (1D optimization)
RIGHT-TO-LEFT (0/1):
w=7 w=6 w=5 w=4 w=3 w=2 w=1
←←←←←←←←←←←←←←←←←←←
dp[w-wt] from previous row → each once ✓
LEFT-TO-RIGHT (unbounded):
w=0 w=1 w=2 w=3 w=4 w=5 w=6
→→→→→→→→→→→→→→→→→→→
dp[w-wt] from current row → reuse ✓
| Variant | Inner Loop Direction | Item Reuse |
|---|
| 0/1 Knapsack | RIGHT-TO-LEFT (downTo) | Each item once |
| Unbounded Knapsack | LEFT-TO-RIGHT | Unlimited reuse |
| Coin Change (min) | LEFT-TO-RIGHT | Unlimited reuse |
When to Use
0/1 knapsackWhy: Each item used at most once. dp[w] iterated RIGHT-TO-LEFT so each item isn't reused within the same pass.
unbounded knapsackWhy: Items reusable. dp[w] iterated LEFT-TO-RIGHT — allows same item to contribute multiple times.
target sum (+/-)Why: Assign + or - to each number. Reduces to 0/1 knapsack: find subsets summing to (target+total)/2.
last stone weight iiWhy: Partition stones into two groups minimizing |sum1-sum2|. = 0/1 knapsack with target total/2.
ones and zeroesWhy: 2D knapsack: capacity is (m zeros, n ones). Each string costs (zeros, ones). Max strings fitting.
- RIGHT-TO-LEFT for 0/1 (each item once) — this is the #1 DP pitfall
- LEFT-TO-RIGHT for unbounded (item reuse)
▶ Visualize
// Longest Palindromic Subsequence
fun longestPalindromeSubseq(s: String): Int {
val n = s.length
val dp = Array(n) { IntArray(n) }
for (i in n - 1 downTo 0) {
dp[i][i] = 1
for (j in i + 1 until n)
dp[i][j] = if (s[i] == s[j]) dp[i+1][j-1] + 2
else maxOf(dp[i+1][j], dp[i][j-1])
}
return dp[0][n - 1]
}
// Longest Palindromic Substring — expand around center
fun longestPalindrome(s: String): String {
var start = 0; var maxLen = 1
fun expand(l: Int, r: Int) {
var left = l; var right = r
while (left >= 0 && right < s.length && s[left] == s[right]) {
if (right - left + 1 > maxLen) {
start = left; maxLen = right - left + 1
}
left--; right++
}
}
for (i in s.indices) { expand(i, i); expand(i, i + 1) }
return s.substring(start, start + maxLen)
}
When to Use
longest palindromic subsequenceWhy: LPS(s) = LCS(s, reverse(s)). Or interval DP: dp[i][j] = LPS of s[i..j]. If s[i]==s[j] → dp[i+1][j-1]+2.
longest palindromic substring (expand)Why: DP: dp[i][j] = true if s[i..j] is palindrome. Or expand-around-center: O(n²) time, O(1) space.
palindrome partitioning (min cuts)Why: dp[i] = min cuts for s[0..i]. Precompute isPalin[i][j], then dp[i] = min(dp[j-1]+1) for palindromic s[j..i].
count palindromic substringsWhy: Expand from each center (odd and even length). Count all expansions that remain palindromic.
- Subsequence: LCS(s, reverse(s)) or interval DP
- Substring: expand-around-center for O(1) space
▶ Visualize
// Regex: . matches any char, * matches 0+ of preceding
fun isMatchRegex(s: String, p: String): Boolean {
val m = s.length; val n = p.length
val dp = Array(m + 1) { BooleanArray(n + 1) }
dp[0][0] = true
for (j in 2..n)
if (p[j-1] == '*') dp[0][j] = dp[0][j-2]
for (i in 1..m)
for (j in 1..n)
dp[i][j] = if (p[j-1] == '*') {
dp[i][j-2] || (p[j-2] == '.' || p[j-2] == s[i-1]) && dp[i-1][j]
} else {
(p[j-1] == '.' || p[j-1] == s[i-1]) && dp[i-1][j-1]
}
return dp[m][n]
}
// Wildcard: ? matches any char, * matches any sequence
fun isMatchWildcard(s: String, p: String): Boolean {
val m = s.length; val n = p.length
val dp = Array(m + 1) { BooleanArray(n + 1) }
dp[0][0] = true
for (j in 1..n)
if (p[j-1] == '*') dp[0][j] = dp[0][j-1]
for (i in 1..m)
for (j in 1..n)
dp[i][j] = if (p[j-1] == '*') dp[i-1][j] || dp[i][j-1]
else (p[j-1] == '?' || p[j-1] == s[i-1]) && dp[i-1][j-1]
return dp[m][n]
}
When to Use
regex matchingWhy: '.' = any char, '*' = zero+ of preceding. dp[i][j] = does s[0..i-1] match p[0..j-1]? Handle '*' as zero or more.
wildcard matchingWhy: '?' = any single char, '*' = any sequence. dp[i][j]: '*' → dp[i-1][j] || dp[i][j-1].
interleaving stringWhy: Can s3 be formed by interleaving s1 and s2? dp[i][j] = s3[i+j-1] matches s1[i-1] or s2[j-1] from valid state.
- * in regex matches zero or more of preceding element
- * in wildcard matches any sequence of characters
- Both need careful base cases for empty patterns
▶ Visualize
// Subset Sum
fun subsetSum(nums: IntArray, target: Int): Boolean {
val dp = BooleanArray(target + 1)
dp[0] = true
for (num in nums)
for (t in target downTo num) // RIGHT-TO-LEFT (0/1)
dp[t] = dp[t] || dp[t - num]
return dp[target]
}
// Partition Equal Subset Sum
fun canPartition(nums: IntArray): Boolean {
val total = nums.sum()
if (total % 2 != 0) return false
return subsetSum(nums, total / 2)
}
// Target Sum (+/- assignment)
fun findTargetSumWays(nums: IntArray, target: Int): Int {
val total = nums.sum()
if ((total + target) % 2 != 0 || total < Math.abs(target)) return 0
val subsetTarget = (total + target) / 2
val dp = IntArray(subsetTarget + 1)
dp[0] = 1
for (num in nums)
for (t in subsetTarget downTo num)
dp[t] += dp[t - num]
return dp[subsetTarget]
}
When to Use
subset sumWhy: Can a subset sum to target? dp[j] = dp[j] || dp[j-num]. Boolean 0/1 knapsack. O(n × target).
partition equal subsetWhy: Can array be split into two equal-sum halves? Equivalent to subset sum with target = total/2.
target sum (+/-)Why: Assign +/- to each number to reach target. P-N=target, P+N=total → P=(target+total)/2. Count subsets summing to P.
partition to k equal subsetsWhy: Bitmask DP or backtracking. Track which elements used (mask) and current bucket sum modulo target.
- Boolean knapsack — right-to-left for 0/1 constraint
- Partition = subset sum of total/2
- Target sum reduces to subset sum via algebra
▶ Visualize
Advanced DP Patterns
// Matrix Chain Multiplication
fun matrixChainMultiplication(dims: IntArray): Int {
val n = dims.size - 1
val dp = Array(n) { IntArray(n) { Int.MAX_VALUE } }
for (i in 0 until n) dp[i][i] = 0
for (len in 2..n)
for (i in 0..n - len) {
val j = i + len - 1
for (k in i until j)
dp[i][j] = minOf(dp[i][j],
dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1])
}
return dp[0][n - 1]
}
// Burst Balloons
fun maxCoins(nums: IntArray): Int {
val a = intArrayOf(1) + nums + intArrayOf(1)
val n = a.size
val dp = Array(n) { IntArray(n) }
for (len in 2 until n)
for (i in 0 until n - len) {
val j = i + len
for (k in i + 1 until j)
dp[i][j] = maxOf(dp[i][j],
dp[i][k] + dp[k][j] + a[i]*a[k]*a[j])
}
return dp[0][n - 1]
}
When to Use
matrix chain multiplicationWhy: dp[i][j] = min cost to multiply matrices i..j. Try all split points k. O(n³).
burst balloonsWhy: Think about which balloon to burst LAST in range [i,j]. dp[i][j] = max coins from range. O(n³).
minimum cost merge stonesWhy: Merge k consecutive piles. dp[i][j] = min cost. Only mergeable when (j-i) % (k-1) == 0.
palindrome partitioning min cutsWhy: dp[i][j] = min cuts for s[i..j]. Interval DP with palindrome precomputation.
optimal bstWhy: Given search frequencies, minimize expected search cost. Try each key as root in range [i..j]. Classic interval DP.
- dp[i][j] = best answer for range [i..j]
- Try all split points k between i and j
- Fill by increasing interval length
▶ Visualize
// Single Transaction
fun maxProfitI(prices: IntArray): Int {
var minPrice = Int.MAX_VALUE; var maxProfit = 0
for (p in prices) {
minPrice = minOf(minPrice, p)
maxProfit = maxOf(maxProfit, p - minPrice)
}
return maxProfit
}
// Unlimited Transactions
fun maxProfitII(prices: IntArray): Int {
var profit = 0
for (i in 1 until prices.size)
if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1]
return profit
}
// With Cooldown (hold / sold / rest states)
fun maxProfitCooldown(prices: IntArray): Int {
var hold = Int.MIN_VALUE; var sold = 0; var rest = 0
for (p in prices) {
val prevSold = sold
sold = hold + p // sell: hold → sold
hold = maxOf(hold, rest - p) // buy: rest → hold
rest = maxOf(rest, prevSold) // cooldown: sold → rest
}
return maxOf(sold, rest)
}
// With Transaction Fee
fun maxProfitWithFee(prices: IntArray, fee: Int): Int {
var hold = -prices[0]; var cash = 0
for (i in 1 until prices.size) {
cash = maxOf(cash, hold + prices[i] - fee)
hold = maxOf(hold, cash - prices[i])
}
return cash
}
When to Use
best time: 1 transactionWhy: Track min price so far. Profit = price - minSoFar. O(n), O(1). Not really DP — just greedy scan.
best time: unlimited transactionsWhy: Capture every upward move. Greedy: profit += max(0, price[i] - price[i-1]).
best time: at most k transactionsWhy: dp[t][i] = max profit using t transactions by day i. Track maxDiff for O(k×n) optimization.
best time: with cooldownWhy: State machine: hold/sold/rest. hold[i] = max(hold[i-1], rest[i-1]-price). sold[i] = hold[i-1]+price. rest[i] = max(rest[i-1], sold[i-1]).
best time: with feeWhy: Two states: cash and hold. cash = max(cash, hold+price-fee). hold = max(hold, cash-price).
- Define states (hold, sold, rest) and transitions between them
- Write transition equations — each state depends on previous states
- Single transaction is simply tracking min price seen so far
▶ Visualize
// Travelling Salesman Problem
fun tsp(dist: Array<IntArray>): Int {
val n = dist.size
val ALL = (1 shl n) - 1
val dp = Array(1 shl n) { IntArray(n) { Int.MAX_VALUE / 2 } }
dp[1][0] = 0 // start at city 0
for (mask in 1..ALL)
for (u in 0 until n) {
if (mask and (1 shl u) == 0) continue
for (v in 0 until n) {
if (mask and (1 shl v) != 0) continue
val next = mask or (1 shl v)
dp[next][v] = minOf(dp[next][v], dp[mask][u] + dist[u][v])
}
}
return (0 until n).minOf { dp[ALL][it] + dist[it][0] }
}
// Partition into K Equal Sum Subsets
fun canPartitionKSubsets(nums: IntArray, k: Int): Boolean {
val total = nums.sum()
if (total % k != 0) return false
val target = total / k
val n = nums.size
val dp = IntArray(1 shl n) { -1 }
dp[0] = 0
for (mask in 0 until (1 shl n)) {
if (dp[mask] == -1) continue
for (i in 0 until n) {
if (mask and (1 shl i) != 0) continue
if (dp[mask] + nums[i] > target) continue
dp[mask or (1 shl i)] = (dp[mask] + nums[i]) % target
}
}
return dp[(1 shl n) - 1] == 0
}
When to Use
tsp (small)Why: dp[mask][i] = min cost visiting cities in mask, ending at i. O(2^n × n²). Only feasible for n ≤ 20.
partition to k equal subsets (bitmask)Why: dp[mask] = sum of elements in mask. Valid if bucket sums work modulo target. O(n × 2^n).
shortest superstringWhy: dp[mask][i] = shortest string using words in mask, ending with word i. Precompute overlaps between all pairs.
can i win (game theory)Why: Bitmask tracks chosen numbers. dp[mask] = can current player force a win? Minimax with memoization.
parallel courses / task assignmentWhy: Bitmask tracks completed tasks. dp[mask] = min time to complete tasks in mask respecting dependencies.
- Mask represents which elements are visited/used as a subset
- dp[mask][i] = best result ending at i with mask visited
- Only works for small n (≤ 20) due to exponential states
▶ Visualize
// Unique BSTs (Catalan number)
fun numTrees(n: Int): Int {
val dp = IntArray(n + 1)
dp[0] = 1; dp[1] = 1
for (i in 2..n)
for (j in 1..i)
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]
}
When to Use
unique BSTs (count)Why: Each root i splits into left (i-1 nodes) × right (n-i nodes). dp[n] = Σ dp[i-1]×dp[n-i]. Catalan numbers.
unique BSTs II (generate all)Why: Same recurrence but build actual trees. For each root, recursively generate all left and right subtrees.
valid parentheses countWhy: Catalan number C(n) = number of valid arrangements of n pairs. Same recurrence as unique BSTs.
number of full binary treesWhy: Full binary tree with n leaves: Catalan(n-1). Each decomposition = left subtree × right subtree.
- dp[n] = Σ dp[i-1] × dp[n-i] for i = 1..n
- Catalan sequence: 1, 1, 2, 5, 14, 42, ...
// Max Path Sum in Binary Tree
fun maxPathSum(root: TreeNode?): Int {
var best = Int.MIN_VALUE
fun dfs(node: TreeNode?): Int {
if (node == null) return 0
val left = maxOf(0, dfs(node.left))
val right = maxOf(0, dfs(node.right))
best = maxOf(best, left + right + node.val)
return maxOf(left, right) + node.val
}
dfs(root)
return best
}
// Diameter of Binary Tree
fun diameterOfBinaryTree(root: TreeNode?): Int {
var best = 0
fun depth(node: TreeNode?): Int {
if (node == null) return 0
val l = depth(node.left)
val r = depth(node.right)
best = maxOf(best, l + r)
return maxOf(l, r) + 1
}
depth(root)
return best
}
When to Use
binary tree max path sumWhy: At each node: pathThrough = val+leftGain+rightGain (both branches). Return val+max(left,right) upward (one branch only).
diameter of binary treeWhy: Same pattern: left+right at each node = path through it. Track global max. Return max(left,right)+1 upward.
house robber IIIWhy: Return (rob, skip) per node. rob = val + skip(children). skip = max(rob, skip) per child. DP on tree structure.
longest zigzag pathWhy: DP on tree: each node tracks best path going left vs going right. Swap direction at each level.
- Return value bottom-up: gain per subtree for the parent
- Track global answer via closure variable (can fork at any node)
- Can't fork when reporting upward — must pick one branch
// Dungeon Game — work backwards
fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
val m = dungeon.size; val n = dungeon[0].size
val dp = Array(m + 1) { IntArray(n + 1) { Int.MAX_VALUE } }
dp[m][n - 1] = 1; dp[m - 1][n] = 1
for (i in m - 1 downTo 0)
for (j in n - 1 downTo 0) {
val need = minOf(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
dp[i][j] = maxOf(1, need)
}
return dp[0][0]
}
When to Use
dungeon gameWhy: Work BACKWARDS: dp[i][j] = min health needed entering (i,j). Forward doesn't work because you need to survive every step.
cherry pickupWhy: Two paths simultaneously: dp[r1][c1][r2], c2 derived. Both collectors move in sync, share cherries at same cell.
cherry pickup ii (two robots)Why: Two robots from top corners, moving down. dp[row][c1][c2] = max cherries. 3D DP, O(m×n²).
out of boundary pathsWhy: dp[steps][r][c] = number of paths that exit grid. 3D DP with modular arithmetic.
- Dungeon works backwards — compute minimum health needed, not gained
- Cherry pickup uses two simultaneous paths
- Reduce dimensions where possible (e.g., 4D → 3D)
▶ Visualize
Common Pitfalls
// PITFALL 1: Wrong state definition
// ✗ dp[i] = "answer" (too vague)
// ✓ dp[i] = "min cost to reach step i" (precise)
// PITFALL 2: Wrong base cases
// ✗ dp[0] = nums[0] (not always correct)
// ✓ Think: what is the answer for the trivial subproblem?
// PITFALL 3: Wrong fill order
// ✗ Filling dp[i][j] before dp[i-1][j-1] is ready
// ✓ Ensure dependencies are computed first
// PITFALL 4: Knapsack direction error
for (w in wt..W) // ✗ LEFT-TO-RIGHT for 0/1 → reuses items!
for (w in W downTo wt) // ✓ RIGHT-TO-LEFT for 0/1 → each item once
// PITFALL 5: Integer overflow
val dp = IntArray(n) // ✗ Can overflow for large values
val dp = LongArray(n) // ✓ Use Long for counting/large sums
// PITFALL 6: Subsequence vs Substring confusion
// Subsequence: elements in order, not necessarily contiguous
// Substring: elements in order AND contiguous
// PITFALL 7: Off-by-one in table size
val dp = IntArray(n) // ✗ Often need n+1 for base case at index 0
val dp = IntArray(n + 1) // ✓ Extra slot for empty prefix/base case
// PITFALL 8: Greedy vs DP
// Coins = [1, 3, 4], amount = 6
// Greedy: 4+1+1 = 3 coins ✗
// DP: 3+3 = 2 coins ✓
- State definition is the hardest part — be precise about what dp[i] means
- Always verify base cases with small examples
- 0/1 knapsack = right-to-left inner loop (the #1 pitfall)
- Use Long for large values to avoid integer overflow
- Subsequence ≠ substring — different recurrences entirely
Quick Reference
| Algorithm | Time | Space |
|---|
| Fibonacci | O(n) | O(1) |
| Climbing Stairs | O(n) | O(1) |
| House Robber | O(n) | O(1) |
| Coin Change | O(n×amount) | O(amount) |
| LIS | O(n²) / O(n log n) | O(n) |
| Max Subarray | O(n) | O(1) |
| Decode Ways | O(n) | O(1) |
| Word Break | O(n²×L) | O(n) |
| Jump Game | O(n) | O(1) |
| Perfect Squares | O(n√n) | O(n) |
| Algorithm | Time | Space |
|---|
| Unique Paths | O(m×n) | O(n) |
| LCS | O(m×n) | O(n) |
| Edit Distance | O(m×n) | O(n) |
| 0/1 Knapsack | O(n×W) | O(W) |
| Palindromic Subseq | O(n²) | O(n) |
| Regex Matching | O(m×n) | O(n) |
| Subset Sum | O(n×target) | O(target) |
| Matrix Chain | O(n³) | O(n²) |
| Burst Balloons | O(n³) | O(n²) |
| TSP | O(2^n×n²) | O(2^n×n) |
| Stock Problems | O(n) | O(1) |
| Unique BSTs | O(n²) | O(n) |
| Dungeon | O(m×n) | O(n) |
| Signal | Pattern |
|---|
| min/max of something | Linear DP |
| count ways | Counting DP |
| two strings comparison | 2D DP |
| grid traversal | Grid DP |
| items + capacity | Knapsack |
| range/interval optimization | Interval DP |
| buy/sell decisions | State Machine |
| subset of ≤ 20 elements | Bitmask DP |
| tree structure | Tree DP |
Linear 1D dp[i] depends on dp[i-1], dp[i-2], ...
Two-String 2D dp[i][j] compares s1[0..i] with s2[0..j]
Grid 2D dp[i][j] from dp[i-1][j] and dp[i][j-1]
Knapsack dp[w] with items — direction matters!
Interval dp[i][j] over range [i..j], try all splits k
State Machine finite states with transitions (hold/sold/rest)
Bitmask dp[mask] where mask encodes subset, n ≤ 20
- State definition is always step 1 — get this right before coding
- Write the recurrence on paper before implementing
- Optimize space only after correctness is confirmed