给定 n=20 个点的无向带权图，边权为正整数，求从 0 号点出发、经过每个点恰好一次的最短路径长度（不要求回到起点）。你用什么状态表示？状态数大约多少？转移怎么写？时间复杂度是多少？如果 n=25，内存 256MB，你还能直接用这个状压 DP 吗？如果边权有负数呢？
面试官在考什么
判断是否理解状压 DP 的状态设计、位运算转移和适用规模边界。
回答框架 · 前两步
- dp[mask][i] 表示已访问点集为 mask、当前停在点 i 的最短路径长度；mask 第 k 位为 1 表示点 k 已访问。
- 转移：dp[mask|(1<<j)][j]=min(dp[mask][i]+w[i][j])，其中 i∈mask，j∉mask。
还有 3 条答案要点、 3 层追问、 6 个常见坑， 以及针对你简历的追问路径，在定制报告里。
延伸阅读
想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页
同一能力域的其他题
- 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。你会怎么设计枚举顺序和滚动数组？如果还要求输出任意一个最长回文子序列，滚动数组还缺什么信息？