位运算与位掩码状态 · HTML
数学 / 逻辑形态
dp[mask] 表示恰完成集合 mask 后的最优值；转移添加 i：next=mask|(1<<i)，或从 mask 删除最后元素。
识别信号
- n 小而顺序或匹配组合巨大
- 未来只依赖已用元素集合
- 不同路径会到达同一集合
- 访问所有节点一次
- 分配、配对或旅行式状态
容易误判的相似信号
| Signal | Why it is different |
|---|
| 未来还依赖未编码历史 | 若最后位置、资源量等影响转移，必须加入额外维度。 |
| n 太大 | 2^n 状态本身不可行，需结构优化或不同算法。 |
核心不变量
dp[mask] 是所有恰形成 mask 的合法序列中最优者；只从已正确的较小状态转移。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 长度 2^n 的 dp；必要时加 last、remaining 等最小充分维度。 |
| Transition | 枚举未选 i，从 dp[mask] 加 transition_cost(mask,i) 松弛 dp[mask|1<<i]。 |
| Frontier / order | 按 bit_count 递增处理集合；所有前驱少一个元素，天然形成 DAG。 |
Python 骨架
def min_order_cost(n, step_cost):
inf = float('inf')
dp = [inf] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == inf: continue
for i in range(n):
if mask >> i & 1: continue
nxt = mask | (1 << i)
dp[nxt] = min(dp[nxt], dp[mask] + step_cost(mask, i))
return dp[-1]
正确性思路
- 空集合基例最优。
- 任何非空方案都有一个最后加入元素 i，删除它得到严格更小前驱。
- 枚举全部前驱与最后选择覆盖所有合法方案。
- 取 min 保留同一 mask 的最优路径，归纳得到最终最优。
复杂度
| Time | Space | Parameters |
|---|
| 典型 O(n2^n)，带 last 可能 O(n²2^n) | O(2^n) 或 O(n2^n) | n 为可选择元素数 |
边界条件
- dp[0] 基例
- 不可达状态保持 inf
- n=0 时 full mask 为 0
- 成本可负但状态图无环
- 额外 last 是否可由 mask 推出
错误模式
| Pattern | Why it fails / fix |
|---|
| 状态信息不足 | 同一 mask 的不同 last 若未来不同就不能合并。 |
| 重复选择元素 | 转移前必须检查对应位未设置。 |
| 无穷值继续运算 | 跳过不可达状态以免污染或溢出。 |
选择与排除规则
- 未来只依赖已选集合：dp[mask]。
- 未来还依赖最后位置：dp[mask][last]。
- 只需枚举不求最优：bitmask enumeration。
- n 超过约 22 时先估算状态量并寻找结构。
相关模板
| Relation | Template | Boundary |
|---|
| aggregation-alternative | 约束满足回溯 | 只求最优/计数且已用集合足以定义状态。 |
| alternative | 0/1 / 完全背包 DP | 物品数小而容量巨大，集合状态更紧凑。 |
| aggregation-alternative | 排列回溯 | 只求遍历/匹配集合的最优值而非列出排列。 |
| 一般化 | 有限状态机 DP | 状态不是纯集合而是有限自动机 |
| 搜索替代 | 子集 / 组合回溯 | 强剪枝可避开多数 mask |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 8 个 mask 复用所有到达同一集合的顺序。 |
| Scenario | 三项任务，每项成本依赖此前已做集合。 |
| Walkthrough | 例如 011 可由 001 加任务 1 或 010 加任务 0，dp[011] 保留更小成本。 |
Recall prompts
我的补充