The Cheapest Way to Pair Everyone Up
n people, with n even, are to be split into n / 2 pairs. Pairing person i with person
j costs c[i][j], and the matrix is symmetric. Print the smallest total cost.
4 people, costs 1-2:1 1-3:5 1-4:9 2-3:8 2-4:4 3-4:2 -> 3 pairs 1-2 and 3-4
2 people, cost 13 -> 13
## Why the cheapest pair first is wrong
Taking the globally cheapest pair, removing it, and repeating is the obvious rule, and the
fourth test is built to break it: the pairs 1-2, 3-4 and 5-6 each cost 1 and everything
else costs 9. There the greedy happens to win.
The fifth test is the one that matters: 1-3 and 2-4 cost 1 each, everything else 10. The
greedy takes 1-3, then must pair 2 with 4, which is also 1, so it ties. Build the trap
yourself before trusting any greedy here: it is easy to find matrices where the cheapest edge
is in no optimal matching, and the table never has to care.
## The same skeleton as 585
Identical structure, with + replaced by min and the count replaced by a cost:
dp[mask] = cheapest way to pair up exactly the people in mask
dp[0] = 0
let i = the lowest index NOT in mask
for each j > i not in mask:
dp[mask | (1<<i) | (1<<j)] = min(that, dp[mask] + c[i][j])
The answer is dp[full].
The lowest-free rule is still needed, for a different reason: without it the table does the
same work 2^{n/2} times over, which is slow rather than wrong.
## Why only even masks are reachable
Every transition sets two bits, so only masks with an even number of bits are ever written.
The odd ones stay at infinity and are skipped by the if unreachable, continue guard. There
is no need to test parity explicitly, and adding such a test is a chance to get the boundary
wrong.
## Cost
Time O(2^n * n). Space O(2^n).
At n = 16 that is about a million steps.
## Boundaries
Two people take the only pair. A matrix where every cost is the same answers that cost times
n / 2, which is a free check on the pair count.