状态压缩动态规划

状态压缩动态规划（State Compression Dynamic Programming）是一种通过将多个状态信息压缩到一个整数或一个较小的状态表示中的动态规划技巧。它常用于解决涉及多个布尔状态或小范围整数状态的问题。状态压缩动态规划通常用于处理组合爆炸问题，尤其是在图论、集合覆盖、路径问题等场景中。

关键概念

1. 状态表示：通过一个整数的二进制表示来编码多个布尔变量。例如，如果有 n 个布尔变量，则可以用一个长度为 n 的二进制数来表示状态，其中二进制数的每一位（0 或 1）对应一个布尔变量的取值。
2. 状态转移：根据问题的要求，通过从当前状态向下一个状态转移，更新动态规划数组。转移过程通常涉及对二进制状态进行操作（如按位与、按位或、按位异或等）。
3. 初始状态：通常是所有变量为 0 或某个特定的初始配置。
4. 终止条件：一般为所有变量达到目标状态，或者枚举完所有可能的状态。

示例：旅行商问题（TSP）

旅行商问题是状态压缩动态规划的经典应用之一。假设有 n 个城市，旅行商需要访问每个城市一次并回到起点，最小化总路程。我们可以用一个二进制数来表示城市的访问状态，其中第 i 位为 1 表示城市 i 已经被访问过。

状态表示

令 dp[S][i] 表示当前状态为 S，并且最后访问的城市是 i 时的最小总路程。其中 S 是一个二进制数，表示哪些城市已经被访问过。

状态转移方程

dp[S | (1 << j)][j] = min(dp[S | (1 << j)][j], dp[S][i] + dist[i][j]);

这里，S | (1 << j) 表示在状态 S 的基础上，加入城市 j；dist[i][j] 是城市 i 到城市 j 的距离。

初始状态

dp[1 << i][i] = dist[0][i];

表示从起点出发，访问城市 i。

终止条件

最终的结果是 dp[AllVisited][0]，其中 AllVisited 表示所有城市都被访问过（即 S = (1 << n) - 1）。

优点和局限

• 优点：能够有效处理组合爆炸问题，将问题规模缩小。
• 局限：状态数量仍然可能是指数级，适用于状态数量相对较小的问题。

应用场景

• 旅行商问题（TSP）
• 最小路径覆盖问题
• 集合覆盖问题
• 字符串匹配问题
• 子集和问题