Using bits of an integer to represent subsets as the DP state.
Bitmask Dynamic Programming is a powerful technique used to solve problems that involve states representing subsets of a collection of items, especially when the number of items is small (typically up to around 20-22). The core idea is to use the bits of an integer as a 'mask' to represent a subset. For `n` items, a mask can be an integer from 0 to `2^n - 1`. If the `i`-th bit in the mask is set to 1, it signifies that the `i`-th item is included in the subset; if it's 0, the item is not included. This allows us to use an array, `dp[mask]`, to store the solution for the subproblem corresponding to the subset represented by `mask`. A classic example of a problem solvable with bitmask DP is the Traveling Salesperson Problem (TSP) on a small number of cities. The state can be defined as `dp[mask][i]`, representing the minimum cost to visit the cities in the subset `mask`, ending at city `i`. The state transition would then involve trying to extend this path to an unvisited city `j`. While the complexity is still exponential, e.g., O(n^2 * 2^n) for TSP, it's a significant improvement over a naive O(n!) brute-force approach.