专题进阶 · 动态规划推荐总顺序 · 第 74 / 148 课

用位集合和终点共同描述访问状态,理解指数状态的可用规模。

先学会这些,再进入本课 二维 DP 集合
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

状态压缩 DPBitmask DP

用位集合记录已选元素,适合元素数量较小的子集状态问题。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用位集合和终点共同描述访问状态,理解指数状态的可用规模。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

从城市 0 出发访问每个城市恰好一次并回到 0,求最短巡回。只知道访问了几个城市为什么不够?

02一步步得到方法

集合内容决定下一步还能去哪里

mask 的第 v 位为 1 表示城市 v 已访问;dp[mask][u] 表示从 0 出发、恰好访问 mask、最后停在 u 的最小代价。相同 mask 但不同终点仍有不同未来成本,所以终点也是必要维度。

转移到未访问 v 时,newmask=mask|(1<<v),更新 dp[newmask][v]。初值仅 dp[1][0]=0,其余无穷;所有城市访问后再加回 0 的边。

位运算只是集合编码

1<<v 对应单元素集合,mask&(1<<v) 检查成员,| 表示加入。它没有神奇地消除指数规模:n 个元素有 2^n 个子集,适用范围通常是十几到二十左右,具体还取决于语言和内存。

从小 mask 向大 mask 扫描可行,因为加入未置位位后数值严格增加。也可按集合大小分层,直接体现先少后多的依赖。

集合相同也可能还需要位置

位掩码编码已选或已访问集合,但旅行路径接下来能去哪里还依赖当前终点,所以状态是 dp[mask][last]。不要因集合可以压成一个整数就省掉其他必要信息。

遍历未访问元素时,可通过位运算检查与添加。状态数约 n2^n,转移再枚举下一点可能达到 n²2^n;压缩的是状态表示,不是把指数规模变成多项式。

03把一个小例子完全算清楚

距离矩阵 [[0,2,9],[1,0,6],[15,7,0]],有向成本。

步骤计算与状态为什么这样做
初始dp[001][0]=0只访问城市 0
访问一座新城dp[011][1]=2,dp[101][2]=9两种首步
访问全部经 1 再 2 成本 8;经 2 再 1 成本 16终点不同
回到 08+15=23;16+1=17取 17

窄屏可左右滑动表格,阅读完整计算与理由。

只有 visited 集合不足以确定路径成本,还必须知道当前位置。

04为什么这个方法成立

  1. 初态代表合法空行程。
  2. 每次只加未访问城市,保证恰好访问集合中的各点一次。
  3. 任一合法巡回删去最后一步都落入某个更小状态,因此转移覆盖全部候选,最终取最小正确。

05把推导翻译成代码

Python · 可独立运行的教学实现

def tsp(cost):
    n = len(cost)
    if n <= 1:
        return 0
    dp = [[float("inf")]*n for _ in range(1<<n)]
    dp[1][0] = 0
    for mask in range(1<<n):
        for u in range(n):
            if dp[mask][u] == float("inf"):
                continue
            for v in range(n):
                if not mask & (1<<v):
                    nxt = mask | (1<<v)
                    dp[nxt][v] = min(dp[nxt][v],dp[mask][u]+cost[u][v])
    return min(dp[-1][u]+cost[u][0] for u in range(1,n))

逐个理解关键决定

dp[1][0] = 0
二进制 001 表示起点已访问,不能从 mask=0 出发后重复访问起点。
mask | (1<<v)
加入一个元素,其他访问记录保留。

06时间、空间与实现范围

O(n2^n) 个状态,每个枚举 n 个后继,时间 O(n²2^n),空间 O(n2^n)。

Python 的嵌套列表和对象开销很大,n=25 也可能远超可用内存;先估状态数再分配。

07改变条件,检查哪里会出错

状态只记录已访问数量

不同城市集合允许的后续完全不同,会错误合并子问题。

把位压缩理解为指数复杂度消失

整数位运算方便枚举,但可能集合数仍是2^n,适用规模需要估算。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

mask=101₂ 表示哪些城市?

需要一点提示

从最低位编号 0。

查看解析与答案

城市 0 与 2。

练习 2 · 边界与辨析

n=20 有多少子集?

需要一点提示

计算 2 的幂。

查看解析与答案

1,048,576 个,还需乘终点维度 20 才是状态槽位数量。

练习 3 · 变式与迁移

改成最少成本完成任务分配,位集合表示什么?

需要一点提示

哪些任务已经分配。

查看解析与答案

mask 可记录已分配任务,当前人员数由 popcount(mask) 推出,此时可能省掉独立位置维度。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。