算法刷题系列（五十四）：状压 DP——用位掩码表示集合状态

算法刷题系列（五十四）：状压 DP——用位掩码表示集合状态

当问题需要记住“哪些项目已经选过”，而项目数量较小，可以用整数的二进制位表示集合。状态压缩 DP（状压 DP）通常有 2^n 个集合状态，再把当前所在位置或阶段加入状态。

本文求一个小型有向带权图中，从 0 号点出发、每个点恰好访问一次的最短路径（不要求回到起点）。这是路径问题，不是要求闭环的旅行商环路。

一、状态与转移

用 mask 的第 v 位表示顶点 v 是否已访问。定义：

dp[mask][v] = 已访问集合为 mask，且最后停在 v 时的最小路径长度

只有当 mask 包含 v 时，该状态才可能有效。若从 u 有边到 v，且 u 已访问、v 未访问，则：

nextMask = mask | (1 << v)
dp[nextMask][v] = min(dp[nextMask][v], dp[mask][u] + weight[u][v])

初始化 dp[1 << start][start] = 0。答案是完整集合中所有可能终点的最小值。

二、例子：四个站点的最短全访问路径

考虑无向边及权重：0-1: 2、0-2: 9、1-2: 3、1-3: 7、2-3: 1。从 0 出发，路径 0→1→2→3 长度为 6，访问每个顶点一次。由于不要求回到 0，不必再增加返程边。

一个状态如 mask = 0111₂、v = 2 表示顶点 0、1、2 已访问，当前在 2。状态中集合与末尾位置都不可缺少：仅有集合无法区分从不同末点延伸时的边权差异。

三、正确性说明

任一访问集合恰含 k 个顶点的合法路径，最后一个顶点 v 之前必有一个前驱 u。删除最后的 v 后得到访问集合 mask 去掉 v 的路径，其代价加上边 u→v 即为原路径代价。转移枚举所有可能的前驱，因此覆盖所有合法路径。反过来，只有在 v 未访问且存在边时才扩展，故不会重复访问顶点或使用不存在的边。按集合大小递增处理，子状态总是先于扩展状态。

四、Java 实现

import java.util.Arrays;

public class BitmaskDp {
    public static long shortestVisitAll(long[][] weight, int start) {
        if (weight == null) {
            throw new IllegalArgumentException("weight must not be null");
        }
        int n = weight.length;
        if (n == 0 || n > 20 || start < 0 || start >= n) {
            throw new IllegalArgumentException("require 1 <= n <= 20 and a valid start");
        }
        for (long[] row : weight) {
            if (row == null || row.length != n) {
                throw new IllegalArgumentException("weight must be square");
            }
        }

        int stateCount = 1 << n;
        long infinity = Long.MAX_VALUE / 4;
        long[][] dp = new long[stateCount][n];
        for (long[] row : dp) {
            Arrays.fill(row, infinity);
        }
        dp[1 << start][start] = 0;

        for (int mask = 0; mask < stateCount; mask++) {
            for (int from = 0; from < n; from++) {
                if (dp[mask][from] == infinity || (mask & (1 << from)) == 0) {
                    continue;
                }
                for (int to = 0; to < n; to++) {
                    if ((mask & (1 << to)) == 0 && weight[from][to] >= 0) {
                        int nextMask = mask | (1 << to);
                        dp[nextMask][to] = Math.min(
                                dp[nextMask][to], dp[mask][from] + weight[from][to]);
                    }
                }
            }
        }

        long answer = infinity;
        for (long distance : dp[stateCount - 1]) {
            answer = Math.min(answer, distance);
        }
        return answer == infinity ? -1 : answer;
    }

    public static void main(String[] args) {
        long[][] weight = {
            {-1, 2, 9, -1},
            {2, -1, 3, 7},
            {9, 3, -1, 1},
            {-1, 7, 1, -1}
        };
        if (shortestVisitAll(weight, 0) != 6
                || shortestVisitAll(new long[][]{{-1}}, 0) != 0) {
            throw new AssertionError("bitmask DP test failed");
        }
    }
}

权重 -1 表示没有边，其他权重需非负。对负权图，有限状态仍能避免重复顶点，但需重新考虑输入约定与溢出边界；本实现明确不将负数当作有效边。

五、Python 实现

def shortest_visit_all(weight, start):
    if weight is None:
        raise ValueError("weight must not be None")
    n = len(weight)
    if n == 0 or n > 20 or not 0 <= start < n:
        raise ValueError("require 1 <= n <= 20 and a valid start")
    if any(row is None or len(row) != n for row in weight):
        raise ValueError("weight must be square")

    infinity = float("inf")
    dp = [[infinity] * n for _ in range(1 << n)]
    dp[1 << start][start] = 0

    for mask in range(1 << n):
        for source in range(n):
            if dp[mask][source] == infinity or not (mask & (1 << source)):
                continue
            for target in range(n):
                edge = weight[source][target]
                if not (mask & (1 << target)) and edge >= 0:
                    next_mask = mask | (1 << target)
                    dp[next_mask][target] = min(
                        dp[next_mask][target], dp[mask][source] + edge
                    )

    answer = min(dp[(1 << n) - 1])
    return -1 if answer == infinity else answer

graph = [
    [-1, 2, 9, -1],
    [2, -1, 3, 7],
    [9, 3, -1, 1],
    [-1, 7, 1, -1],
]
assert shortest_visit_all(graph, 0) == 6
assert shortest_visit_all([[-1]], 0) == 0

六、复杂度与状态规模

状态数最多 2^n × n，每个状态尝试 n 个下一顶点，时间复杂度 O(2^n n²)，空间复杂度 O(2^n n)。指数增长使该方法只适合较小的 n；实际可接受上限取决于语言、内存和转移数量。

七、边界与常见错误

1. 只保存已访问集合：还需要记录当前末点，才能判断下一条边及路径成本。
2. 状态扩展时允许访问已访问点：会破坏“每点一次”的条件。
3. 把路径问题写成环路问题：是否返回起点必须按题意另加最后一条边。
4. 把无边与零权边混淆：本实现用 -1 表示无边，0 表示合法零权边。
5. 忽视指数规模：n 增加 1，集合状态数翻倍；约束必须在分配大数组前检查。
6. 哨兵值参与加法溢出：只从可达状态转移，并使用安全的无穷哨兵。

小结

位掩码紧凑地表示一个小集合，DP 再把“集合 + 当前阶段”作为状态。先确认哪些历史信息会影响后续决策；在本例中，访问集合与末点共同决定可行后继与代价。