bitmask DP
Sometimes the natural state of a subproblem is 'which members of a small set have I dealt with so far?' — which cities have I visited, which tasks are assigned, which people are seated. A subset of a set with n elements can be encoded as an n-bit binary number: bit i is 1 if element i is in the subset and 0 if not. Bitmask DP indexes the DP table by these subset-numbers, so a number from 0 to 2^n - 1 is a complete description of which elements are 'done'. With n up to about 20, there are at most a million or so subsets, which is tractable.
Each integer mask from 0 to 2^n - 1 names a subset, and dp[mask] (often with a second index) stores the best answer for the situation where exactly the elements in mask have been handled. Transitions flip bits: to add element j to the subset you compute mask | (1 << j); to test whether j is present you check (mask >> j) & 1; to iterate over present elements you loop over set bits. The order of evaluation is by increasing popcount or simply by increasing integer value, since a mask's transitions usually go to masks with one more bit set (a strict superset), and 'mask with one extra bit' is a larger integer. The canonical use is assignment-style problems: dp[mask] = best cost to assign the first popcount(mask) jobs to exactly the workers in mask, transitioning by giving the next job to some unused worker.
The cost is the killer feature and the killer limit at once. There are 2^n subsets and each transition examines up to n bits, so a typical bitmask DP runs in O(2^n times n) time and O(2^n) space — exponential, but a vast improvement over the O(n!) of trying all orderings. That keeps n small: around 20 is comfortable, 25 is pushing memory, and beyond roughly 30 the 2^n blows up. The most famous instance is the Held-Karp algorithm for the travelling salesman problem. Bitmask DP is the right tool precisely when n is small enough that exponential-in-n is acceptable and the state genuinely is 'which subset', not when n is large.
Assign n tasks to n workers, cost[i][j] for worker i doing task j. dp[mask] = min cost to assign the first popcount(mask) tasks using exactly the workers in mask. Transition: for the next task t = popcount(mask), try each unused worker w: dp[mask | (1<<w)] = min(dp[mask | (1<<w)], dp[mask] + cost[w][t]). Answer dp[(1<<n) - 1].
An integer's bits ARE the subset; flipping a bit is adding an element.
Bitmask DP only beats brute force because it merges all orderings that reach the same subset into one state; if the answer truly depends on the order you arrived, not just the set, then the subset is not a valid state and you cannot collapse it this way.