In n-worker n-shift assignment DP, why does dp[mask] alone suffice with no worker index?

## The setup n workers must each be given exactly one of n shifts, one worker per shift, with a cost matrix `cost[w][s]` giving what it costs to put worker w on shift s (overtime premium, travel, skill mismatch). Minimise total cost. There are n! assignments; at n = 15 that is over a trillion. Subset DP brings it to 2^n states. ## The state and its invariant Define `dp[mask]` = the minimum cost of assigning workers 0..k−1 to exactly the shifts whose bits are set in `mask`, where **k = the number of set bits in mask**. That sentence contains the entire insight. Workers are processed in a fixed order — worker 0, then worker 1, and so on — and each transition consumes one worker *and* one shift. The two counts therefore move in lockstep and can never diverge. Whose turn it is is not extra information; it is derivable from the state you already have. ## The recurrence ``` dp[0] = 0 for mask = 1 to 2^n - 1: k = number of set bits in mask // shifts filled = workers placed dp[mask] = INFINITY for s in 0..n-1: if bit s of mask is set: prev = mask with bit s cleared dp[mask] = min(dp[mask], dp[prev] + cost[k-1][s]) answer = dp[2^n - 1] ``` Read the last worker placed as `k−1` because `mask` already includes their shift. Increasing numeric order over masks is a valid evaluation order: clearing a bit always yields a smaller number, so `dp[prev]` is final when read. Complexity is 2^n states × O(n) transitions = O(2^n·n) time and O(2^n) memory — an n-fold saving over the naive `dp[mask][worker]` formulation in both. ## Why the redundant dimension is not harmless Engineers often shrug at an extra index: "it is only a factor of n, and it makes the code clearer." Three reasons to care. 1. **Memory is the binding constraint in subset DP.** A factor of n at n = 22 is more than four million extra entries per mask-layer's worth of table — the difference between fitting and not, and it costs you roughly four elements of headroom against a wall you are already close to. 2. **It manufactures unreachable states.** In `dp[mask][w]`, every pair where `w` is not the set-bit count of `mask` is meaningless. They will be initialised, iterated and cache-missed. Worse, a bug that writes to one of them will produce an answer that looks plausible and is wrong, because nothing in the loop structure declares those states illegal. 3. **It hides the invariant.** The clean formulation forces you to state "filled shifts = processed workers", which is the property a reviewer or an interviewer actually wants to hear. Carrying both lets you avoid noticing that they are the same number. ## When the shortcut breaks — the part that matters The count implies the index only when **each transition advances both counters by exactly one**. Break that coupling and the shortcut is wrong: - **Optional items.** If a worker may be left unassigned (fewer shifts than workers, or a "no suitable shift" option), then a mask with three bits could correspond to having considered three, four or five workers. The index is no longer a function of the mask and must be stored. - **Multiplicity.** If one worker can cover two shifts, two set bits can belong to one worker. Same failure. - **Order-dependent cost.** If the cost of placing a worker depends on *which* shift the previous worker took — a handover, a shared vehicle, a travel leg between locations — then even with the counters coupled you need the previous choice in the state, which is the routing shape with its extra endpoint dimension. So the two archetypes are mirror images. In a routing DP the extra dimension is mandatory because steps are coupled through the last choice. In a plain assignment DP it is redundant because steps are coupled only through *how many* have been made. Being able to say which situation you are in, and why, is what separates a memorised template from understanding the state design. ## Practical notes Initialise unreached entries to infinity, not zero, or partial garbage propagates into the answer as a suspiciously cheap schedule. To recover the actual roster, either store the winning shift per mask or walk backwards from the full mask, at each step finding the `s` whose removal satisfies the equality in the recurrence. And if the matrix is rectangular — more shifts than workers — index the mask over the *smaller* dimension; the exponent is where all your cost lives, so it should sit on whichever side is smaller.