Sign in to watch this lesson
Advanced - Dynamic Programming · 4:35
Bitmask DP: TSP, Assignment & SOS
When the state of a problem is a set of used items, we store it as a bitmask. We replace the (n-1)! orders of a route with Held-Karp's table over (visited set, last venue), solve the assignment problem with a DP over the mask alone, and compute sums over all submasks for every mask in n·2ⁿ steps instead of 3ⁿ by adding along one bit at a time, as on the edges of a cube.
You will learn
- Model a route as the state (set of visited items, last item) and fill Held-Karp's table in O(2^n·n^2) time, reconstructing the route from stored predecessors
- Solve assignment-type problems with dp[mask] alone, using popcount(mask) as the index of the next worker, in O(2^n·n)
- Compute F[mask] = sum of A over all submasks for every mask in O(n·2^n) with the bit loop outermost, and explain why swapping the loops overcounts
- Estimate time and memory before coding (2^20 × 20 long long is about 168 MB) and fix the start city for cycles