有 n 个城市（n ≤ 18），任意两城之间的距离 d[i][j] 已知，求从 0 号城市出发、每个城市恰好经过一次、最后回到 0 号城市的最短回路。你用 f[mask][i] 来做：(1) mask 和 i 分别表示什么，mask 的第 k 位为 1 代表什么？(2) 写出状态转移，特别是怎么枚举"下一步要去哪"。 (3) 状态数和总时间复杂度分别是多少，n 取到多少时这个做法就基本不能用了？
面试官在考什么
判断候选人是否真正理解"用一个整数的二进制位表示集合"这个核心思想，以及是否具备估算状态规模、知道算法适用边界的能力。
回答框架 · 前两步
- mask 是一个 0 到 2^n - 1 的整数，第 k 位为 1 表示城市 k 已经访问过，用整数的位当集合用。
- f[mask][i] 表示"已经访问的城市集合是 mask、当前停在城市 i"的最小路径长度；初始 f[1<<0][0] = 0，其余为无穷大。
还有 3 条答案要点、 3 层追问、 5 个常见坑， 以及针对你简历的追问路径，在定制报告里。
延伸阅读
想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页
同一能力域的其他题
- 01 背包场景：n=1000 件物品，背包容量 W=100000，每件物品重量 w_i、价值 v_i，每件最多选 1 件，求最大总价值。你写一维数组 DP，代码里容量循环写成 for (int j=W; j>=w[i]; --j)，而不是 for (int j=w[i]; j<=W; ++j)。请解释这两种写法在 01 背包和完全背包下分别会得到什么结果，为什么？如果把条件改成每种物品最多选 2 件，你会怎么改？
- 0-1 背包精确求解。实例 A：n=100，W=10^9，每个 w_i 可达 10^9，v_i<=1000；实例 B：n=40，W=10^9，w_i 和 v_i 可达 10^12。单次预算 1 秒。你会分别选什么算法？请给出状态定义、复杂度，并说明为什么不能都写成 dp[W]。
- 你在做一个离线批处理调度器：每天凌晨要在一台 128 核的机器上，从 N=2000 个待跑任务里挑一个子集执行，每个任务有 CPU 需求 w_i（1~200 的整数核）和业务收益 v_i，目标是总收益最大。需求要求最终输出被选中的任务清单，而不是只输出最优收益值，且整个求解要在 5 秒内完成。同事给的方案是标准 0/1 背包 DP。请说明你会怎么实现（状态定义、空间处理、方案还原），并回答：如果第二天任务数变成 200000、机器换成 10000 核的聚合池，同一套代码还能不能撑住，你会怎么改。
- 有 N 件物品，第 i 件体积 w[i]、价值 v[i]，每件物品只能用一次，背包容量为 W。用一维数组 f[0..W] 写 0/1 背包时，内层容量循环必须写成 for (j = W; j >= w[i]; --j)。请说明为什么必须倒序，并自己举一个具体的数值例子（给出 w、v、W），把正序循环时数组被更新的过程一步步算出来，说明会出什么错。
- 给定长度为 n=500 的数组 a，每次可以合并相邻两个数，代价为两数之和，合并后新数放回原位置。求把所有数合并成一个数的最小总代价。你定义的状态是什么？转移方程怎么写？为什么枚举区间长度而不是只枚举起点？时间、空间复杂度各是多少？如果数组是环形的，即首尾也相邻，你怎么处理？
- 给定字符串 s，长度 n=5000，求最长回文子序列长度。区间 DP 转移是 s[i]==s[j] 时 dp[i][j]=dp[i+1][j-1]+2，否则 max(dp[i+1][j], dp[i][j-1])。O(n^2) 时间约 25e6 可接受，但 dp[n][n] 的 int 约 100MB，内存限制 64MB。你会怎么设计枚举顺序和滚动数组？如果还要求输出任意一个最长回文子序列，滚动数组还缺什么信息？