Bitmask DP
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.
Lessons
1. Introduction to Bitmask DP
Subsets as binary numbers
2. What Bitmask DP Solves
TSP, assignments, partitions
3. When to Use Bitmask DP
n ≤ 20 and tracking used elements
4. Problem - TSP
Visit all cities, return home
5. TSP - Why Naive Fails
n! to 2^n × n
6. TSP - Defining the DP
dp[mask][i] = end at city i
7. TSP - Transition
Which city did we come from?
8. TSP - Base Cases
Start at city 0, mask = 1
9. TSP - Implementation
O(2^n × n²) triple loop
10. TSP - Time and Space
2^20 × 20 fits in memory
11. TSP - Edge Cases
Asymmetric distances? Self-loops?
12. Lessons from TSP
Order within visited set doesn't matter
13. Problem - Shortest Hamiltonian Path
No return, any start city
14. Shortest Hamiltonian Path - Solution
15. Lessons from Shortest Hamiltonian Path
16. Assignment Problem - Overview
AtCoder DP O - count matchings
17. Assignment Problem - Why Naive Fails
Process men in order 0 to n-1
18. Assignment Problem - Defining the DP
popcount(mask) = men matched so far
19. Assignment Problem - Core Logic
+= instead of min()
20. Assignment Problem - Implementation
2^n states, O(n) per state
21. Lessons from Assignment Problem
Count paths, not shortest path
22. Shortest Superstring - Overview
Precompute suffix-prefix overlaps
23. Shortest Superstring - Why Naive Fails
TSP on overlap graph
24. Shortest Superstring - Defining the DP
computeOverlap for each pair
25. Shortest Superstring - Core Logic
Reconstruct by backtracking
26. Shortest Superstring - Implementation
String concatenation = graph shortest path
27. Lessons from Shortest Superstring
Profile DP on grids
28. Sum over Subsets (SOS) DP - Problem Pattern
One bit at a time, O(n × 2^n)
29. SOS DP - Why Naive Fails
1D array suffices
30. SOS DP - Space-Optimized Implementation
AND pairs, OR maximization
31. SOS DP - Applications
O(3^n) submask enumeration
32. Problem - Elevator Problem
Fit person or start new ride
33. Elevator Problem - Solution
(rides, capacity) pair as state
34. Elevator Problem - State Transition
Tile m×n with dominoes
35. Iterating Over Submasks - Technique
Split set into two parts
36. Iterating Over Submasks - When to Use
Is this bitmask DP?
37. Problem - Special Permutations
dp[mask][last] counting
38. Special Permutations - Solution
LC 1799 - pair for GCD × round
39. Problem - Maximize Score
Pick pairs, multiply by round number
40. Maximize Score - Solution
LC 526 - position divisibility
41. Problem - Beautiful Arrangement
Fill positions left to right
42. Beautiful Arrangement - Solution
Sum over all subsets of mask
43. Quiz: Bitmask DP Patterns
n = 20 overflow, bit indexing
44. Quiz: Bitmask Edge Cases
Bit shift vs popcount errors
45. Common Mistakes in Bitmask DP
Bit shift vs popcount errors
46. Problem - Maximum Students Taking Exam
LC 1349
47. Maximum Students Taking Exam - Implementation
Solution approach
48. Problem - Number of Ways to Wear Different Hats
LC 1434
49. Number of Ways to Wear Different Hats - Implementation
Solution approach
50. Section Recap
From TSP to SOS