~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Bitmask DP
dp[mask][last] over subsets (n <= ~20): TSP, assignment.
Notes
Recognise it when: n <= ~20 and the state is "which items are used" (TSP, assignment, visiting all nodes).
dp[mask][last] = the best cost having visited mask and ending at last. Loop over masks in increasing order and extend with each unvisited nxt: dp[mask | 1 << nxt][nxt].
O(2^n · n^2).
Bit tricks: test with mask >> i & 1, list submasks with sub = (sub - 1) & mask, and use bin(mask).count("1") or mask.bit_count().
7 problems
Advanced & competitive
Advanced DP Bitmask and digit DP.
Bitmask DP
- Basics: cheapest one-to-one job assignment basics py · c++ · java easy
- Pairing up lab partners py · c++ · java easy
- Shortest walk visiting every node py · c++ · java hard
- Fewest work sessions py · c++ · java medium
- Count Hamiltonian routes py · c++ · java medium
- Cheapest way to order everything you want AirbnbConfluent medium
- Every cheapest way to order a meal Airbnb hard