Stage 1 · Code
Dynamic Programming
Bitmask DP
TSP, assignment problems, and state compression with bitmasks.
Bitmask Basics
Bitmask = integer where each bit represents inclusion of an element. n elements → 2^n possible subsets. Bit operations: check (mask & (1<<i)), set (mask | (1<<i)), clear (mask &^ (1<<i)), iterate subsets.
Traveling Salesman Problem (TSP)
Find shortest Hamiltonian cycle visiting all cities exactly once. DP state: dp[mask][i] = min cost to visit cities in mask ending at city i. mask includes i. Transition: dp[mask][i] = min(dp[mask^1<<i][j] + dist[j][i]). Base: dp[1<<0][0] = 0.
Assignment Problem
Assign n workers to n jobs minimizing total cost. DP: dp[mask] = min cost assigning first k workers to jobs in mask, where k = popcount(mask). dp[mask] = min(dp[mask ^ (1<<j)] + cost[k][j]) for j in mask.
Subset DP Patterns
| Pattern | State | Transition | Example |
|---|---|---|---|
| TSP | dp[mask][last] | Add unvisited | Shortest Hamiltonian path |
| Assignment | dp[mask] | Assign next worker | Min cost bipartite matching |
| Subset sum | dp[mask] | Add element | Partition, subset sum |
| Independent set | dp[mask] | Check valid | Max independent set in small graph |
| Steiner tree | dp[mask][v] | Combine subsets | Connect terminals in graph |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.