# LeetCode 1066: Campus Bikes II

## Problem Restatement

We have `n` workers and `m` bikes on a campus.

We need to assign each worker exactly one bike, minimizing the total Manhattan distance between each worker and their assigned bike.

Return the minimum total Manhattan distance.

The official constraints state that `n <= m <= 10` (small, bitmask DP is feasible).

## Input and Output

| Item | Meaning |
|---|---|
| Input | Worker positions and bike positions |
| Output | Minimum total assignment distance |

Function shape:

```python
def assignBikes(workers: list[list[int]], bikes: list[list[int]]) -> int:
    ...
```

## Key Insight

With `m <= 10` bikes, we can represent which bikes have been assigned using a bitmask.

`dp[mask]` = minimum cost to assign `popcount(mask)` workers to the bikes indicated by `mask`.

The `i`-th worker uses bike `j` when bit `j` is set in the mask.

## Algorithm

1. `dp[0] = 0`.
2. For each mask (in order of popcount):
   - Let `i = popcount(mask)` (this is the worker index).
   - For each bike `j` not in the mask:
     - `dp[mask | (1 << j)] = min(..., dp[mask] + dist(worker[i], bike[j]))`.
3. Return the minimum `dp[mask]` where `popcount(mask) == n`.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(2^m * m)` | Process each mask with each bike |
| Space | `O(2^m)` | DP array |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def assignBikes(self, workers: list[list[int]], bikes: list[list[int]]) -> int:
        n, m = len(workers), len(bikes)
        inf = float("inf")
        dp = [inf] * (1 << m)
        dp[0] = 0

        def dist(w, b):
            return abs(w[0] - b[0]) + abs(w[1] - b[1])

        for mask in range(1 << m):
            worker_idx = bin(mask).count('1')
            if worker_idx >= n:
                continue
            for j in range(m):
                if not (mask >> j & 1):
                    new_mask = mask | (1 << j)
                    dp[new_mask] = min(dp[new_mask], dp[mask] + dist(workers[worker_idx], bikes[j]))

        return min(dp[mask] for mask in range(1 << m) if bin(mask).count('1') == n)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.assignBikes([[0,0],[2,1]], [[1,2],[3,3],[2,3]]) == 6
    assert s.assignBikes([[0,0],[1,1],[2,0]], [[1,0],[2,2],[2,1]]) == 4

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| 2 workers, 3 bikes | `6` | Optimal assignment |
| 3 workers, 3 bikes | `4` | Minimum total distance |