##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Explore individual topics with detailed lessons and practice problems.
You know the 0/1 knapsack pattern. Now apply it to harder variants like Tallest Billboard, where constraints and state design push beyond textbook examples.
You've seen range-based DP. Here you solve Matrix Chain Multiplication and Burst Balloons, where you split intervals and combine subproblem answers.
Learn what this roadmap covers, who it's for, and how to get the most out of it.
What this roadmap covers
Prerequisites you need
The sections ahead
Getting the most out of it
You know the 0/1 knapsack pattern. Now apply it to harder variants like Tallest Billboard, where constraints and state design push beyond textbook examples.
Why this family matters
Constraints that scream knapsack
Binary choices, additive limits
LC 956 - equal height supports
Track difference, not both
Difference as the state dimension
Skip, add left, or add right
Both supports empty at start
Hash map for sparse states
Why S not S² in the bound
One dimension beats two
CF 687C - subset of a subset
Track two sums at once
dp[total][partial] = reachable?
Include in total, partial, or skip
dp[0][0] = true, rest false
Reverse iteration avoids reuse
Quadratic in target value
Nested subset constraints
LC 879 - the gang problem
Counting vs optimizing
Cap profit to bound states
+= instead of max()
3D logic in 2D space
Counting with multiple constraints
CF 837D - maximize trailing zeros
Zeros come from min(2s, 5s)
Fix 5s, greedily pick 2s
Knapsack over factor counts
Precompute 2s and 5s
Optimize one, iterate the other
CF 864E - deadlines and values
Sort by deadline first
Time as the knapsack capacity
Must finish before deadline
Reconstruction with backtracking
Scheduling reduces to knapsack
1D array suffices
Why backward for 0/1 knapsack
Each item has a copy limit
Which items made the optimal?
Backtrack through the DP table
Is this knapsack?
Zero capacity, empty arrays
Forward vs backward iteration
LC 2585
Solution approach
CSES 1093
Solution approach
LC 2742
Solution approach
LC 2518
Solution approach
CSES 1628
Solution approach
From 0/1 to bounded to unbounded
You've seen range-based DP. Here you solve Matrix Chain Multiplication and Burst Balloons, where you split intervals and combine subproblem answers.
Merge, split, combine
When subproblems nest inside
CF 607B - remove palindromes
Same endpoints merge free
dp[l][r] = moves to clear
Match ends, split, or single
Empty = 0, single = 1
Bottom-up by length
O(n³) with O(n²) states
LC 1000 - merge k at a time
When is one pile possible?
Piles mod (k-1) matters
Step by k-1 in splits
Prefix sums for merge cost
CF 149D - color matched brackets
Matching structure guides DP
4D state: positions and colors
Inside first, then combine
Stack finds the pairs
LC 1039 - triangulate polygon
One triangle per edge
dp[l][r] for vertex range
Try each apex vertex k
O(n³) for n vertices
LC 1547 - cutting costs
Add 0 and n as boundaries
LC 664 - overwriting printer
Extend matching chars free
LC 546 - group same colors
3D: track trailing boxes
What makes interval DP?
Empty ranges, single elements
Length order, not index order
LC 471
Solution approach
LC 1246
Solution approach
From MCM to Remove Boxes
You've done DP on arrays. Now states live at tree nodes. Solve Binary Tree Max Path Sum and learn how to aggregate child results at each vertex.
Aggregate from subtrees
Diameters, paths, and matchings
No cycles, natural recursion
LC 124 - any path, max sum
The bend point insight
Return vs update: what's the difference?
max(0, child) avoids negatives
Null = 0, leaf = its value
Global update inside DFS
O(n) time, O(h) space
All negative? Skewed tree?
Return one direction, update both
CSES - distance sum per node
Reroot in O(1), not O(n)
Subtree size and subtree sum
Moving root flips distances
First DFS from arbitrary root
Two DFS passes, O(n) total
O(n) beats naive O(n²)
Star graph vs path graph
Reroot when answer depends on root
CF 161D - pairs at distance k
Combine depths across subtrees
cnt[d] = nodes at depth d
Match d and k-d across children
Small-to-large for O(n log n)
Depth counting, not pair enumeration
LC 543 - longest path in edges
leftDepth + rightDepth through node
O(n) single pass
CF 1187E - maximize paint score
Sum of subtree sizes
score[v] = score[u] + n - 2*size[v]
Maximum matching in tree
dp[v][matched] or dp[v][unmatched]
Greedy from leaves up
LC 968 - minimum cameras
Three states: uncovered, covered, has camera
Which subtree pattern is this?
Single node, empty tree
Post-order for bottom-up
LC 2246
Solution approach
From path sum to rerooting
You've handled linear and tree states. Now track subsets with bitmasks. Solve TSP and learn how to iterate over visited elements in exponential state spaces.
Subsets as binary numbers
TSP, assignments, partitions
n ≤ 20 and tracking used elements
Visit all cities, return home
n! to 2^n × n
dp[mask][i] = end at city i
Which city did we come from?
Start at city 0, mask = 1
O(2^n × n²) triple loop
2^20 × 20 fits in memory
Asymmetric distances? Self-loops?
Order within visited set doesn't matter
No return, any start city
AtCoder DP O - count matchings
Process men in order 0 to n-1
popcount(mask) = men matched so far
+= instead of min()
2^n states, O(n) per state
Count paths, not shortest path
Precompute suffix-prefix overlaps
TSP on overlap graph
computeOverlap for each pair
Reconstruct by backtracking
String concatenation = graph shortest path
Profile DP on grids
One bit at a time, O(n × 2^n)
1D array suffices
AND pairs, OR maximization
O(3^n) submask enumeration
Fit person or start new ride
(rides, capacity) pair as state
Tile m×n with dominoes
Split set into two parts
Is this bitmask DP?
dp[mask][last] counting
LC 1799 - pair for GCD × round
Pick pairs, multiply by round number
LC 526 - position divisibility
Fill positions left to right
Sum over all subsets of mask
n = 20 overflow, bit indexing
Bit shift vs popcount errors
Bit shift vs popcount errors
LC 1349
Solution approach
LC 1434
Solution approach
From TSP to SOS
You know basic string matching. Now solve Edit Distance, LCS variants, and two-sequence alignment problems with multi-dimensional DP tables.
Sequences, alignment, transformation
Two strings → dp[i][j]
LC 10 - dot and star patterns
Star means zero or more of previous
dp[i][j] = does prefix match?
Zero times or extend match
Empty vs patterns like a*b*
Handle *, then .
O(mn) both time and space
.* matches everything
Operators create branches
LC 97 - merge two strings
dp[i][j] uses s3[i+j-1]
LC 131 - all palindrome partitions
Precompute isPalin[i][j]
Interval DP for palindrome check
SCS = len1 + len2 - LCS
Backtrack through LCS table
LC 5 - longest palindrome substring
Expand around center or DP
LC 139 - dictionary segmentation
dp[i] = prefix can be split?
Which pattern is this?
Empty string, single char
1-indexed DP, 0-indexed strings
LC 87
Solution approach
LC 730
Solution approach
LC 940
Solution approach
LC 1278
Solution approach
LC 1639
Solution approach
From edit distance to word break
You've optimized single-player decisions. Now handle two players taking turns. Solve Stone Game variants where both sides play to win.
Two players, optimal play
Alternating turns, perfect info
LC 1510 - remove square amounts
Winning if opponent can lose
dp[n] = can current player win?
Try all squares, find losing state
dp[0]=false, dp[1]=true, dp[2]=false
O(n√n) checking squares
√n moves per position
LC 1406 - take 1, 2, or 3
Maximize score difference
dp[i] = advantage from position i
Take stones, subtract opponent's best
dp[n] = 0, no stones left
Right to left, O(n)
O(1) space with sliding window
XOR piles, zero = lose
XOR trick explained
Grundy = mex of reachable states
mex = minimum excludant
XOR Grundy for combined games
Odd steps only matter
Even-to-odd = adding to Nim
XOR Grundy numbers
mex of reachable Grundy values
Topological order on DAG
LC 877 - pick from ends
Interval DP or math trick
Alice always wins (odd total)
LC 1690 - score = remaining sum
Remove stone, score the rest
Prefix sums for range totals
Which game pattern is this?
Single pile, symmetric games
Whose turn? Score difference handles it
LC 913
Solution approach
LC 1872
Solution approach
CSES 2207
Solution approach
From win/lose to Grundy
Advanced digit DP problem-solving techniques
What you'll practice
Quick refresher
Adjacent digit constraint
Track the previous digit
The code
Key takeaways
Count digit occurrences
Count contributions per position
The code
Complexity analysis
Key takeaways
Test your understanding
Limit non-zero digits
Count non-zeros placed
Pruning invalid paths
The code
Key takeaways
Permutations with divisibility
Too many permutations
Track used positions and remainder
The code
Key takeaways
Test your understanding
Position-dependent rules
Enforce different rules at even/odd positions
The code
Complexity analysis
Key takeaways
Palindrome structure
Only half the digits are free
The code
Key takeaways
Test your understanding
Sum instead of count
Return a pair from DP
The code
Complexity analysis
Key takeaways
Divisibility by own digits
Track remainder mod 2520
The code
Complexity analysis
Key takeaways
Test your understanding
Binary digit DP
Work with bits, not decimal digits
The code
Key takeaways
What to watch out for
Comprehensive check
Continue your practice
Summary
