今天是算法与数据结构专题的第16篇，也是动态规划系列的第5篇。

今天文章的内容是动态规划当中非常常见的一个分支——状态压缩动态规划，很多人对于状态压缩畏惧如虎，但其实并没有那么难，希望我今天的文章能带你们学到这个经典的应用。

二进制表示状态

在讲解多重背包问题的时候，我们曾经讲过二进制表示法来解决多重背包。利用二进制的性质，将多个物品拆分成少数个物品，转化成了简单的零一背包来解决。今天的状态压缩同样离不开二进制，不过我个人感觉今天的二进制应用更加容易理解一些。

二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个int整形是4个字节，也就是32位bit，我们通过这32位bit上0和1的组合可以表示多大21亿个不同的数。如果我们把这32位bit看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。

比如上图当中，我们列举了5个二进制位，我们把其中两个设置成了1，其余的设置成了0。我们通过计算，可以得到6这个数字，那么6也就代表了(00110)这个状态。数字和状态是一一对应的，因为每个整数转化成二进制都是的。

也就是说一个整数可以转化成二进制数，它可以代表某个集合的一个状态，这两者一一对应。这一点非常重要，是后面一切推导的基础。

状态转移

整数的二进制表示可以代表一个二元集合的状态，既然是状态就可以转移。在此基础上，我们可以得出另一个非常重要的结论——我们可以用整数的加减表示状态之间的转移。

我们还用刚才的例子来举例，上面的图当中我们列举了5个二进制位，假设我们用这5个二进制位表示5个小球，这些小球的编号分别是0到4。这样一来，刚才的6可以认为表示拿取了1号和2号两个小球的状态。

如果这个时候我们又拿取了3号小球，那么集合的状态会发生变化，我们用一张图来表示：

旅行商问题

NP问题

状态压缩解法

import math

if __name__ == "__main__":
    inf = 1 << 31
    # 邻接矩阵存储边权重
    d = [[inf for _ in range(10)] for _ in range(10)]
    # 测试数据
    edges = [[, 1, 3], [1, 2, 5], [2, 3, 5], [3, 4, 3], [4, , 7], [4, 1, 6], [, 3, 4], [2, , 4]]
    for u, v, l in edges:
        d[u][v] = l

    # 初始化成近似无穷大的值
    dp = [[inf for _ in range(5)] for _ in range((1 << 5))]
    dp[][] = 

    # 遍历状态
    for s in range(1, (1 << 5)):
        for u in range(5):
            # 遍历决策
            for v in range(5):
                # 必须要求这个点没有去过
                if (s >> v) & 1 == :
                    continue
                dp[s][v] = min(dp[s][v], dp[s - (1 << v)][u] + d[u][v])

    print(dp[(1 << 5) - 1][])

    # 我们从0点已经遍历开始
    dp[1][] = 

    for s in range(2, (1 << 5)):
        for u in range(5):
            # 严格限制u必须已经遍历过
            if (s >> u) & 1 == :
                continue
            for v in range(5):
                if (s >> v) & 1 == :
                    continue
                dp[s][v] = min(dp[s][v], dp[s - (1 << v)][u] + d[u][v])

    ans = inf
    # 后加上回到0点的距离
    for i in range(5):
        ans = min(ans, dp[(1 << 5) - 1][i] + d[i][])
        
    print(ans)

总结