有一个构建流水线排序服务：n 个编译单元要排成一个执行序列，先执行 i 再执行 j 的切换代价是 c[i][j]（非负、不对称），目标是序列总代价最小。团队用状态压缩 DP：dp[mask][i] 表示已执行集合为 mask、最后一个执行 i 的最小代价，n=20 时跑得很好。现在业务要求支持 n=26，且允许结果比最优差不超过 3%。请判断原方案还能不能用，说明你会怎么改，以及你怎么向业务解释这个取舍。
面试官在考什么
考察他对 2^n 状态空间的内存和访存特性的直觉，以及能否用可量化的近似方案回应业务诉求，而不是死磕精确解。
回答框架 · 前两步
- 状态数 2^n × n：n=20 约 2e7，n=26 约 1.7e9；即使每状态只存 4 字节也是 GB 级，单机放不下。
- 转移每个状态要枚举下一个 j，整体 O(2^n · n^2)，n=26 时约 4e10，时间和内存双双不成立。
还有 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。你会怎么设计枚举顺序和滚动数组？如果还要求输出任意一个最长回文子序列，滚动数组还缺什么信息？