看到 LintCode 3666 的assignBikesII(int[][] workers, int[][] bikes)这道题，很多人的第一反应是：上一个校园自行车分配不是用优先队列把所有“工人-自行车”距离对排序，然后逐个挑就行了么？这个第二版能难到哪去？等到真正提交时才发现，它要求的是“最小总距离”，本质上是个二分图最优匹配变体，需要从回溯、记忆化搜索一路升级到状态压缩 DP，才算把这题吃透。这篇文章我会用 Java 完整拆一遍三种实现，并且把为什么贪心必挂、状态压缩的 mask 到底怎么设计、以及面试时怎么把这个题讲出层次感，一次性说清楚。
1. 题目到底在算什么：别被“校园自行车”六个字带偏
1.1 把题目翻译成数学语言
这道题的场景很具象：校园里有若干个工人，每个工人有坐标；还有若干个自行车停放点，每个自行车也有坐标。一个工人只能骑一辆车，每辆车也只能被一个工人使用。要求“每位工人都被分配一辆自行车”，同时让所有人走到自己那辆车的曼哈顿距离之和最小。
先看曼哈顿距离怎么算，这是第一层送分点：
// 两个点 (x1, y1) 和 (x2, y2) 的曼哈顿距离 int dist = Math.abs(x1 - x2) + Math.abs(y1 - y2);为什么不直接用欧氏距离？因为题目只允许上下左右移动，实际路径就是横向差加纵向差，曼哈顿距离才是真实代价，不是直线距离。
如果把工人编号为0 ~ n-1，自行车编号为0 ~ m-1，那我们要做的就是从m辆车里挑出n辆出来，和n个工人构成一个一一映射。设工人i分配到自行车bikeOf[i]，目标函数是：
min sum( dist(workers[i], bikes[bikeOf[i]]) ), i = 0..n-1约束条件是：
- 每个工人都分配到一辆自行车。
- 同一辆自行车不能被分配给两个工人。
- 通常保证
m >= n，自行车数量不少于工人数量。
到这一步，题目已经脱离了“按距离排序挑一挑”的模拟题范畴，变成一个组合优化问题。你要在庞大的分配方案集合里搜索代价最小的那一个。
1.2 为什么贪心不成立：亲手画一个 5 分钟反例
如果你以前刷过另一个校园自行车分配题，可能见过“按所有工人自行车的距离排序，从小到大优先分配”的做法。很多第一版题目确实可以贪心通过，但到了assignBikesII，这个套路一定会翻车，因为题目目标明确定义成“全局总距离最小”。
我举个非常小的反例，你画在纸上立刻能懂。
三个坐标点：
工人 W0 = (0, 0) 工人 W1 = (5, 0) 自行车 B0 = (5, 0) 自行车 B1 = (-100, 0)距离矩阵如下：
| 距离 | B0 | B1 |
|---|---|---|
| W0 | 5 | 100 |
| W1 | 0 | 105 |
如果按“从 W0 开始，给每个工人挑一辆当前离他最近、且没被占用”的思路，W0 会看到 B0 距离是 5，B1 距离是 100，于是把 B0 拿走。W1 只能骑 B1，距离 105。总代价是 5 + 105 = 110。
但最优方案是这样：W0 骑 B1，代价 100；W1 骑 B0，代价 0。总代价是 100，比 110 更小。
这个例子说明了什么？B0 虽然离 W0 不算远，但它离 W1 是 0，是 W1 的“专属最优解”。W0 把 B0 抢走，只给自己省了很少的距离，却让 W1 付出了惨痛代价。局部最优的选择叠加起来，不一定是全局最优。
所以这道题别浪费时间证明什么贪心性质了，直接用搜索或者 DP 枚举所有合法分配方案。
1.3 动手写代码前，先把这几个边界条件问清楚
刷题最怕的是看题看一半就写，写完了才发现自己的版本和评测数据对不上。做assignBikesII之前，建议先对着题目确认四件事：
workers.length和bikes.length的取值范围。通常很小，可能只有 10 以内，否则状态压缩 DP 的2^m状态是扛不住的。- 是不是保证
bikes.length >= workers.length。如果自行车比工人少，那“每个工人都分到车”的约束本身就不成立，得换问法。 - 距离计算的单位是曼哈顿距离，不是欧氏距离，千万别在坐标里直接调
Math.hypot。 - 题目要求返回值是
int，那么距离累加不会溢出吗？坐标绝对值通常不会太大，int够用；但如果你在练习时自己改大了数据范围，建议改用long兜底。
我见过不少人在这些地方翻车：有人把自行车数量和工人数量搞反，导致数组越界；有人在状态转移里忘记车少人多的情况；还有人距离矩阵计算错了下标，样例过了但大样例全挂。这些都算不上算法不会，纯粹是细节没锁死。
2. 第一版能跑的方案：回溯 + 剪枝是面试保底答案
2.1 回溯的决策树到底长什么样
先别急着上状态压缩 DP，因为面试时你大概率要先用一个最朴素的方案证明自己理解了问题。
回溯的本质是：从工人 0 开始，一辆车一辆车试。工人 0 可以尝试任意一辆没被占用的自行车；选定之后，工人 1 再从剩余自行车里选一辆……直到所有工人都分配完，记录当前方案的总距离，并和全局最优值比较。
当有n个工人、m辆自行车时，每一个合法分配方案就是从m辆车里按顺序选出n辆，并和工人一一配对。方案的数量的上限大约是：
P(m, n) = m! / (m - n)!如果n = m = 9，那就是 362880 种方案。这个数量级在面试题里可以直接用回溯跑出来。如果n = m = 10，是 3628800 种，纯回溯也勉强能跑，但是加上剪枝会更稳。
这里的决策树可以理解为：每一层对应一个工人，每个节点要去枚举“该工人能骑哪一辆还没被用的自行车”。
2.2 Java 回溯实现
需要一个visited数组或者位掩码来记录哪些自行车已经被占用了。点不多的情况下，我更推荐用位掩码，因为和后面的状态压缩 DP 顺路。
public int assignBikesII(int[][] workers, int[][] bikes) { int n = workers.length; int[] ans = { Integer.MAX_VALUE }; dfs(0, 0, 0, workers, bikes, ans); return ans[0]; } private void dfs(int workerIdx, int bikeMask, int curCost, int[][] workers, int[][] bikes, int[] ans) { if (curCost >= ans[0]) { return; // 剪枝：当前花费已经不可能成为最优 } if (workerIdx == workers.length) { ans[0] = Math.min(ans[0], curCost); return; } for (int j = 0; j < bikes.length; j++) { if ((bikeMask & (1 << j)) != 0) { continue; // 这辆车已经被占用 } int d = Math.abs(workers[workerIdx][0] - bikes[j][0]) + Math.abs(workers[workerIdx][1] - bikes[j][1]); dfs(workerIdx + 1, bikeMask | (1 << j), curCost + d, workers, bikes, ans); } }这段代码最需要理解的是bikeMask的用法。bikeMask是一个整数，它的第j位如果为 1，就表示编号为j的自行车已经被前面的工人选走了；如果为 0，说明空闲。
判断是否占用：(bikeMask & (1 << j)) != 0。
标记占用：bikeMask | (1 << j)。
这种用一个整数的二进制位来记录布尔数组状态的技巧，就是“状态压缩”。你现在就可以在回溯版本里先体会一下，后面 DP 版本本质上是对它的升级。
2.3 剪枝条件不是越多越好
上面代码里只有一个剪枝：当curCost >= ans[0]就无条件返回。这个剪枝在数据随机时效果非常明显，因为一旦找到一个比较小的可行解，很多较差的搜索路径都会被提前掐断。
但要注意它的效果高度依赖“找到好解的速度”。如果你运气差，第一组完整方案就是 10000，那么后续上万条路径在超过 10000 才会被剪掉，效果有限。更稳定的做法是优先按成本低的自行车去尝试，也就是在枚举前先把当前工人的自行车按距离从小到大排序，让更优秀的解更早出现。
不过排序需要花费额外时间和空间，而且回溯版本在真正的大测验数据下依然会超时，所以它更适合作为“我理解这个问题”的面试第一版，而不是作为最终答案。
2.4 回溯的实际瓶颈：重复子问题没有复用
如果你只是背模板，可能看不出来回溯的问题在哪。我举个例子：
工人有 3 个，自行车有 5 辆。某个时刻，我们已经给工人 0 和工人 1 分配了自行车 {B0, B3}，现在要给工人 2 分配；另一个搜索路径上，工人 0 和工人 1 分配的是 {B3, B0}。虽然顺序反了，但剩余可用的自行车集合完全一样，都是 {B1, B2, B4}，而且工人编号都是 2。
这意味着这两个搜索分支后续要处理的问题完全相同，但回溯会傻傻地再算一遍。状态压缩 DP 的目标，就是把这个重复计算给消掉。
3. 进阶状态压缩 DP：把“可用车集合”当作状态
3.1 状态设计的核心意象：每辆车只有被占用和空闲两种状态
状态压缩 DP 的第一步，仍然是选定一个能准确描述“当前局面”的东西。
在回溯里，我们需要两个信息：当前处理到第几个工人了、目前哪些自行车已经被占用了。其实第二个信息拿到后，第一个信息是可以推导出来的——已经分配掉的工人数量，一定等于自行车占用数量。所以一个bikeMask就足够描述状态。
我们定义：
dp[mask] = 已经用 mask 对应的自行车集合，分配给前 k 个工人（k = mask 中 1 的个数）时，前 k 个工人的最小总距离。举个例子：mask = 0b101，二进制低 3 位是 101，表示编号 0 和编号 2 的自行车已经被占用。此时1的个数为 2，也就是已经有 2 个工人被分配完毕，下一个待分配工人下标是 2。
再深入理解一下这个问题为什么天然适合 DP：由于所有工人的坐标是固定的，任意一个“已使用自行车集合”和“即将开始分配的第 k 个工人”唯一决定了一个子问题。后面无论选择哪辆车，都会进入一个新的子问题；而子问题之间不是树形的，而是图状的，存在大量交汇，所以可以缓存。
3.2 状态转移方程
假设当前已经分配了前k个工人，其中k = bitCount(mask)。现在尝试把编号为j的空闲自行车分配给工人k，转移后的状态是：
newMask = mask | (1 << j)代价是：
dp[newMask] = min(dp[newMask], dp[mask] + dist(workers[k], bikes[j]))注意这里有一个隐藏技巧：mask中 1 的数量正好等于“已经分配好的工人个数”，所以下一轮要坐下一个是第几个工人，由Integer.bitCount(mask)直接得到，不用再传单独的工人下标。
如果自行车数量等于工人数量，最终答案是dp[(1 << bikes.length) - 1]，也就是说所有自行车都被使用了。但在实际题里，自行车数量通常可能大于工人数量，所以最终答案要从“恰好用了 n 辆车的状态”里取最小值，而不是傻傻返回所有车都用完的那个状态。
3.3 Java 状态压缩 DP 实现
public int assignBikesII(int[][] workers, int[][] bikes) { int n = workers.length; int m = bikes.length; // dist[i][j]: 工人 i 到自行车 j 的曼哈顿距离 int[][] dist = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dist[i][j] = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]); } } int totalStates = 1 << m; int INF = Integer.MAX_VALUE / 2; int[] dp = new int[totalStates]; Arrays.fill(dp, INF); dp[0] = 0; // 一辆车都没用，0 个工人已分配，代价 0 for (int mask = 0; mask < totalStates; mask++) { int workerIdx = Integer.bitCount(mask); if (workerIdx >= n) { // 所有工人都已经分配完毕，不能再继续加车了 continue; } // 考虑当前这个工人 workerIdx 可以骑哪一辆空闲自行车 for (int j = 0; j < m; j++) { if ((mask & (1 << j)) != 0) { continue; // 车 j 已被占用 } int nextMask = mask | (1 << j); dp[nextMask] = Math.min(dp[nextMask], dp[mask] + dist[workerIdx][j]); } } // 自行车数量可能多于工人数量，找“恰好分配了 n 辆车”的最小值 int ans = INF; for (int mask = 0; mask < totalStates; mask++) { if (Integer.bitCount(mask) == n) { ans = Math.min(ans, dp[mask]); } } return ans; }简单说下为什么遍历mask从 0 到totalStates - 1是安全的：每一次转移都会把一个 0 位改成 1，二进制对应整数会变大，所以nextMask一定大于当前mask。从小到大遍历，保证更新某个状态时，它所有可能的前驱状态都已经被计算好了。
这个版本的复杂度很好估算。状态数大约2^m，每个状态尝试的车辆数不超过m，所以渐进复杂度是O(m * 2^m)，空间复杂度O(2^m)。当m <= 10时，状态数只有 1024，完全可以接受。
3.4 一个最容易忽略的坑：final ans为什么不是dp[全1]
我见过很多同学把状态压缩 DP 写完后，直接返回dp[(1 << m) - 1]，在m == n的测试用例上没问题，但一旦题目改成自行车比工人多，就会全错。
为什么？因为“所有自行车都占用”意味着你已经给超过工人数量的自行车都分配了人，这是不可能的。只要自行车比工人多，一定有一些自行车最终空闲。
所以更通用、更稳的收尾方式是：对所有二进制中 1 的个数恰好等于工人数的状态取最小值。
int ans = Integer.MAX_VALUE; for (int mask = 0; mask < totalStates; mask++) { if (Integer.bitCount(mask) == workers.length) { ans = Math.min(ans, dp[mask]); } } return ans;如果你确定这道题保证n == m，直接返回dp[(1 << n) - 1]也不是不行，但我还是建议写成通用版本，因为这才是这个状态定义的完整语义。
4. 记忆化搜索：比背递推公式更不容易写错的方案
4.1 从回溯到记忆化，只差一个缓存
很多人会觉得状态压缩 DP 的递推顺序需要额外的“拓扑感”，总要小心别把状态之间依赖顺序搞乱。其实有一种更贴合人类直觉的解法：保持回溯那种“从当前状态往后搜索”的思路，但把已经计算过的结果保存下来，避免重复搜索。这就是记忆化搜索。
代码结构和回溯几乎一样，区别在于：
- 回溯遇到完整方案，更新全局最优。
- 记忆化搜索则是用返回值表示“从当前状态开始，完成所有后续分配所需的最小代价”。
比如当前workerIdx等于 3，bikeMask已经占用了某 3 辆车，那么这个子问题的最优值就写到memo[mask]里。即使以后从另一条路径到达同样的 mask，也不需要重算。
4.2 为什么缓存只用一维就够
这是理解这个版本的关键。
回忆一下递归的参数：workerIdx和bikeMask。初始时workerIdx = 0，bikeMask = 0。每分配一辆车，workerIdx加 1，同时bikeMask也会多一个 1 位。所以整个递归过程始终满足：
workerIdx == Integer.bitCount(bikeMask)因此只要给定bikeMask，当前是第几个工人其实是确定的，不需要单独作为缓存维度。这也是为什么很多高效题解只用一个memo[mask]数组。
public int assignBikesII(int[][] workers, int[][] bikes) { int n = workers.length; int m = bikes.length; int totalStates = 1 << m; int[] memo = new int[totalStates]; Arrays.fill(memo, -1); return dfs(0, 0, workers, bikes, memo); } private int dfs(int workerIdx, int bikeMask, int[][] workers, int[][] bikes, int[] memo) { if (workerIdx == workers.length) { return 0; // 所有工人都分配完了，后续代价是 0 } if (memo[bikeMask] != -1) { return memo[bikeMask]; } int best = Integer.MAX_VALUE; for (int j = 0; j < bikes.length; j++) { if ((bikeMask & (1 << j)) != 0) { continue; } int d = Math.abs(workers[workerIdx][0] - bikes[j][0]) + Math.abs(workers[workerIdx][1] - bikes[j][1]); int rest = dfs(workerIdx + 1, bikeMask | (1 << j), workers, bikes, memo); best = Math.min(best, d + rest); } memo[bikeMask] = best; return best; }这个版本在时间复杂度和空间复杂度上和状态压缩 DP 基本一致，也同样不会重复计算同一个子问题。区别只是它是自顶向下的，天然适合那些不擅长设计递推顺序的人，也适合面试时边说思路边写。
4.3 记忆化版本还能随手加剪枝
既然它保留了搜索的外壳，你还可以在dfs开头加一个“当前累计已经超过了最优解”的分支剪枝，如果用一个全局ans来记录已知可行解的话。不过加了之后要注意：因为返回值语义变成了“剩余最小代价”，剪枝判断要放在外层函数操作累计值时使用，并不是在dfs内直接比较。
我个人的建议是：在面试中如果时间紧张，直接用记忆化搜索，思路最好讲，代码最不容易出错，缓存数组开1 << m大小，也不会爆内存。递推版留给追求极致简洁、想展示自己对 DP 熟练度的场景。
5. 复杂度与典型翻车点：提交不过时先查这几个地方
5.1 三种写法复杂度对照
| 写法 | 时间复杂度 | 空间复杂度 | 面试推荐度 |
|---|---|---|---|
| 暴力回溯 + 剪枝 | 最好情况不定，最坏约P(m, n) | 递归深度O(n) | 用作第一版破冰 |
| 状态压缩 DP | O(m * 2^m) | O(2^m) | 最优标准解 |
| 记忆化搜索 | 状态数O(2^m)，每状态尝试O(m) | O(2^m) | 最不容易写错，强烈推荐 |
注意哈希版本如果没有使用数组memo，而是使用HashMap<Integer, Integer>，理论上也没有问题，但常数会稍微高一点。数据范围小，完全无所谓；数据范围一旦到 20 左右，就尽量用数组而不是哈希表。
5.2 位运算这里最容易出 bug
状态压缩核心就是位运算，看似简单，实际坑不少。
第一个常见 bug：1 << j的优先级。如果你写if ((mask & 1 << j) == 0)，Java 会先算1 << j，但由于&的优先级低于==，很可能会编译报错或逻辑混乱。我建议任何时候都加上括号，写成(mask & (1 << j)) == 0，宁可多一个括号也不要省。
第二个常见 bug：把自行车和工人编号搞混。dp[mask]里的mask表示自行车的占用情况，不是工人的占用情况。如果你把bitCount(mask)和工人编号匹配错，结果完全是错的。
第三个常见 bug：对Integer.MAX_VALUE直接做加法。在状态转移里，如果dp[mask]还是无穷大，你贸然加上dist，在 Java 里会溢出变成负数，然后Math.min反而把负数当成最小值，结果全乱。因此初始化要留够余量，比如Integer.MAX_VALUE / 2。
第四个常见 bug：递归的记忆化版本中，缓存数组初始值-1和实际代价冲突吗？不会，因为曼哈顿距离是非负整数，最小代价可能是 0，所以初始化为-1是安全哨兵。如果你用0作为初始值，那么代价本来为 0 的子问题就会被误判成“还没计算过”，导致潜在错误。
5.3 自己造数据做小规模对拍
不管你是新手还是老手，做这种搜索类题目，特别建议自己写一个暴力枚举的“最朴素版本”来对拍。
朴素版本可以用递归枚举每个工人的分配，不剪枝、不记忆化，保证逻辑最简单。跑小数据时，把它和状态压缩 DP 的结果对比，如果两个结果相同，说明 DP 状态定义没问题；如果不同，就打印所有中间状态，看是哪个转移出了问题。
我在刷这题时用的自测数据结构是：
- 工人和自行车坐标随机生成，范围在
[0, 5]，这样距离矩阵小，肉眼可验算。 - 分别尝试
n = 2, m = 2、n = 2, m = 3、n = 3, m = 4几组数据。 - 每组数据都从暴力回溯和 DP 两种写法分别跑一遍，验证结果一致。
有一次就是靠随机数据发现了一个问题：我的代码里把工人总数和自行车总数写反了，导致m > n时返回的结果偏大。这种问题如果只做官方样例，根本看不出来。
6. 同一个题型还能怎么延伸：面试官换问法的应对思路
6.1 如果自行车比工人少，如何套用现有代码
原题大概率保证自行车数量不少于工人数量，但面试官可能会说“我现在只保证自行车数量小于工人”，问你能不能继续做。
这种情况下，“每个工人都分配车”不成立，就必须明确新目标。如果问题改成“尽量让更多工人骑到车，在人数最多的前提下最小化总距离”，那问题就不一样了。现有状态压缩 DP 仍然可以用，但最终更新答案的条件不再是“恰好分配 n 辆车”，而是“找到能分配的最大人数 t”，再在bitCount(mask) == t的所有状态里取最小代价。
一种更省事的方法是把状态转移改成：当前工人可以选择“不分配自行车”，作为跳过处理；然后最终通过人数优先的方式更新答案。
6.2 如果目标改成“让跑得最远的那个工人距离最小”
这是一个更常见、也更符合直觉的变体：不再求总距离最小，而是让“所有工人中距离最大的那个”尽量小。
解法也不需要完全推翻。状态压缩 DP 的框架可以保留，但转移时不再累加距离，而是用：
dp[nextMask] = min( dp[nextMask], max(dp[mask], dist[workerIdx][j]) )这样每一个状态保存的就不是“总代价”，而是“当前分配方案中的最大单点距离”。最终答案是从所有恰好分配完的状态中取最小最大值。这个版本在面试里非常常见，理解了原题之后，扩展起来就是几分钟的事。
顺便说一句，这种“最小化最大值”的问法有时还会搭配二分答案：先猜一个最大距离上限limit，然后只允许分配距离不超过limit的自行车，再看是否存在合法方案。不过数据量小的时候，直接用上面的 DP 更简单。
6.3 大数据版本：匈牙利算法和最小费用最大流
如果把数据范围扩大，比如工人和自行车数都到了几百，状态压缩 DP 的2^m肯定会爆炸。这时候问题就变成一个标准的二分图最小权匹配，可以直接用匈牙利算法求最小权完美匹配，或者用最小费用最大流建模。
不过面试里直接问几百规模校园自行车分配的概率不高，大多数情况是考你从搜索到状态压缩的优化思路。如果面试时你能主动提一句“当 m 到 15 以上，O(m * 2^m) 会超时，这时我会考虑二分图匹配算法”，就足以证明你不是背了模板，而是真的理解复杂度的来源。
我个人实际刷这题时的体会是：状态压缩 DP 确实是为解决“多退少补”的重复子问题而生的，但如果一上来就背代码，很容易把mask的含义搞混。建议你先亲手把回溯版写一遍，再在它的基础上加缓存，让代码自己告诉你“为什么这个状态只需要一个整数”。
把这件事想通了，以后遇到类似的“小规模配对最小代价”问题，比如座位分配、任务分配、旅行商简化版，你都会条件反射地去想：这个决策集合能不能压成一个 int 的各位状态？如果能，那基本就是状态压缩 DP 没跑了。
