Bitmask DP

Concepts: pyBitmaskDP, pyTSP, pyAssignment

Bitmask DP encodes a subset of elements as a bitmask (integer). If bit k of the mask is 1, element k is 'used' or 'included.' This lets you use the mask as a DP state, representing which elements have been visited. The classic problem is Traveling Salesman Problem (TSP) with small n. You cannot solve TSP in polynomial time for large n, but for n <= 20, bitmask DP gives you O(n^2 * 2^n) which is tractable. The dp[mask][i] Pattern dp[mask][i] = optimal cost when you have visited exactly the cities in 'mask' and are currently at city i. The transition: to extend the path, pick any unvisited city j (bit j is not set in mask) and update dp[mask | (1 << j)][j]. Start at dp[1 << 0][0] = 0 (visited only city 0, currently at city 0). The answer is the minimum over all masks with all cities visited