第29篇-状态压缩DP-当状态很多时如何降维优化

概述为什么需要状态压缩 DP前面我们讲过线性 DP、背包 DP 和区间 DP。这些 DP 的状态通常比较直观dp[i] dp[i][j]但有些问题的状态不是一个位置、一个容量或一个区间而是一组元素是否已经被选择比如哪些任务已经完成哪些城市已经访问哪些数字已经使用哪些人已经被分配工作如果直接用数组或集合去表示这些状态代码会很复杂。这时就可以使用状态压缩 DP。状态压缩 DP 的核心思想是用一个整数的二进制位表示一组选择状态本篇会重点讲什么是状态压缩二进制状态如何表示集合如何枚举状态和判断某一位任务分配问题怎么写状态压缩 DPTSP 类问题的基本模板常见坑点和复杂度分析学完这篇你应该能看懂mask、1 i、dp[mask]这类写法并能用二进制集合解决小规模选择问题。核心概念什么是状态压缩状态压缩就是把一个复杂状态压成一个整数。假设有4个任务编号为0, 1, 2, 3我们可以用一个四位二进制数表示哪些任务已经完成。0000 表示一个任务都没完成 0001 表示任务 0 已完成 0010 表示任务 1 已完成 0101 表示任务 0 和任务 2 已完成 1111 表示 4 个任务都已完成这里每一位都代表一个元素的选择状态0没有选1已经选为什么可以用整数表示因为二进制位天然就是一组开关。一个整数有很多二进制位每一位都可以表示一个元素是否存在。这就把“集合”变成了“数字”。状态压缩就是用二进制位表示集合用整数表示复杂选择状态。位运算基础状态压缩必须掌握的操作状态压缩 DP 经常用到这些位运算。1. 表示第 i 位1i例如1 0 0001 1 1 0010 1 2 01002. 判断第 i 位是否为 1(mask(1i))!0如果结果不为0说明第i位是1。3. 把第 i 位设置为 1mask|(1i)这表示把元素i加入集合。4. 把第 i 位设置为 0mask~(1i)这表示把元素i从集合中移除。5. 判断集合是否包含某个元素if((mask(1i))!0){// i 已经被选择}6. 枚举所有状态如果有n个元素总状态数是2^n代码写成for(intmask0;mask(1n);mask){// 处理状态 mask}状态压缩 DP 的基础操作就是检查某一位、添加某一位和枚举所有二进制状态。为什么状态数量是2^n每个元素都有两种状态不选选如果有n个元素那么总状态数就是2 * 2 * 2 * ... * 2 2^n例如n 3时所有状态是000 001 010 011 100 101 110 111一共8个。状态压缩适合多大规模因为状态数量是指数级所以状态压缩 DP 一般适合n 20如果转移里还要再枚举一个元素复杂度通常是O(n * 2^n)如果还要枚举两个元素可能变成O(n^2 * 2^n)状态压缩不是把指数级问题变成线性而是把可控范围内的指数状态表示得更高效。经典模型任务分配的最小成本先看一个很适合入门的状态压缩 DP。题目描述有n个工人和n个任务cost[i][j]表示第i个工人做第j个任务的成本。每个工人只能做一个任务每个任务也只能被一个工人做求最小总成本。例如cost [ [9, 2, 7], [6, 4, 3], [5, 8, 1] ]要给每个工人分配一个不同任务使总成本最小。为什么适合状态压缩因为我们需要记录哪些任务已经被分配如果任务数量不大就可以用一个mask表示任务集合。任务分配问题的核心状态是已经使用过哪些任务。状态定义dp[mask]表示什么定义dp[mask] 表示已经分配了 mask 中这些任务时的最小成本例如mask 101表示任务0和任务2已经被分配。当前应该给哪个工人分配任务如果mask里有k个1说明已经分配了k个任务。那么下一个要分配任务的工人就是第 k 个工人在 Java 里可以用intworkerInteger.bitCount(mask);Integer.bitCount(mask)会返回mask中1的个数。mask记录任务集合bitCount(mask)决定当前轮到哪个工人。状态转移枚举下一个任务当前状态是mask当前工人是worker。我们要枚举一个还没有被分配的任务job。如果任务job没有被选过(mask(1job))0那么可以把它分配给当前工人。新状态是nextMaskmask|(1job)转移方程是dp[nextMask] min(dp[nextMask], dp[mask] cost[worker][job])初始状态一开始没有任何任务被分配dp[0] 0其他状态初始化为一个很大的数。最终答案所有任务都被分配时mask (1 n) - 1所以答案是dp[(1 n) - 1]从当前任务集合出发选择一个没用过的任务加入集合并更新最小成本。Java 实现任务分配最小成本importjava.util.Arrays;classSolution{publicintminCost(int[][]cost){intncost.length;inttotalStates1n;int[]dpnewint[totalStates];Arrays.fill(dp,Integer.MAX_VALUE/2);dp[0]0;for(intmask0;masktotalStates;mask){intworkerInteger.bitCount(mask);if(workern){continue;}for(intjob0;jobn;job){if((mask(1job))0){intnextMaskmask|(1job);dp[nextMask]Math.min(dp[nextMask],dp[mask]cost[worker][job]);}}}returndp[totalStates-1];}}代码关键点totalStates 1 n总状态数是2^ndp[0] 0没有分配任何任务时成本为0Integer.bitCount(mask)根据已分配任务数确定当前工人nextMask把新任务加入集合dp[totalStates - 1]所有任务都被分配后的最小成本任务分配模型是状态压缩 DP 的标准入门题核心是用mask表示已经选过的任务。用一个小例子走一遍状态假设有3个任务。初始状态mask 000 dp[000] 0此时bitCount(000) 0轮到工人0。可以选择任务0、1、2000 - 001 000 - 010 000 - 100下一轮如果状态是mask 010说明任务1已经被分配。此时bitCount(010) 1轮到工人1。还能选择任务0或任务2010 - 011 010 - 110最终会走到111也就是所有任务都已经分配完成。每次转移都是从一个集合状态走向多选一个元素的新集合状态。状态压缩 DP 的常见形式状态压缩 DP 常见状态有两类。一维状态dp[mask]这种状态只关心集合本身。例如任务分配dp[mask] 表示已经选了 mask 这些任务时的最小成本常见转移从 mask 添加一个新元素得到 nextMask二维状态dp[mask][i]这种状态不仅关心集合还关心当前停在哪个元素。例如旅行商问题dp[mask][i] 表示已经访问 mask 这些城市并且当前停在城市 i 的最短距离这里的i很重要因为下一步从哪里出发会影响代价。如果只关心选了哪些元素用dp[mask]如果还关心当前停在哪里用dp[mask][i]。经典模型TSP 旅行商问题旅行商问题是状态压缩 DP 的经典模型。题目简化描述有n个城市任意两个城市之间有距离。从城市0出发访问每个城市一次最后回到城市0求最短路径。状态定义dp[mask][i] 表示已经访问 mask 中的城市并且当前停在城市 i 的最短距离初始化从城市0出发dp[1][0] 0这里1的二进制是0001表示只访问了城市0。状态转移如果当前停在城市i下一步去城市j并且城市j没访问过nextMask mask | (1 j) dp[nextMask][j] min(dp[nextMask][j], dp[mask][i] dist[i][j])最终答案访问完所有城市后还要回到城市0ans min(dp[fullMask][i] dist[i][0])其中fullMask (1 n) - 1TSP 需要dp[mask][i]因为不仅要知道访问了哪些城市还要知道当前在哪个城市。Java 模板TSP 状态压缩 DPimportjava.util.Arrays;classSolution{publicinttsp(int[][]dist){intndist.length;inttotalStates1n;int[][]dpnewint[totalStates][n];intinfInteger.MAX_VALUE/2;for(int[]row:dp){Arrays.fill(row,inf);}dp[1][0]0;for(intmask0;masktotalStates;mask){for(inti0;in;i){if((mask(1i))0){continue;}for(intj0;jn;j){if((mask(1j))!0){continue;}intnextMaskmask|(1j);dp[nextMask][j]Math.min(dp[nextMask][j],dp[mask][i]dist[i][j]);}}}intfullMasktotalStates-1;intansinf;for(inti1;in;i){ansMath.min(ans,dp[fullMask][i]dist[i][0]);}returnans;}}为什么要判断城市i在mask里因为dp[mask][i]的含义要求当前停在城市 i并且城市 i 已经被访问如果i不在mask中这个状态本身就是无效的。为什么城市j不能在mask里因为旅行商问题要求每个城市访问一次。如果j已经访问过就不能再访问。mask控制已经访问的城市i控制当前所在城市j控制下一步去哪里。子集枚举状态压缩里的进阶技巧有些题需要枚举一个集合的所有子集。例如给定mask 1110你可能需要枚举它的所有非空子集。常见写法是for(intsubmask;sub0;sub(sub-1)mask){// sub 是 mask 的一个非空子集}为什么这样能枚举子集sub - 1会改变二进制低位结构再和mask做与运算就能保证结果始终是mask的子集。这个技巧在集合划分、分组 DP 中很常见。包含空集怎么办如果也要处理空集可以在循环结束后单独处理// sub 0或者使用do while但初学阶段建议写清楚一点。sub (sub - 1) mask是枚举某个集合所有子集的经典写法。状态压缩 DP 的常见题型状态压缩 DP 常见于这些场景。1. 选择集合类题目会问哪些元素已经选过哪些任务已经完成哪些数字已经使用常用状态dp[mask]2. 路径访问类题目会问已经访问了哪些点当前停在哪个点访问所有点的最小代价常用状态dp[mask][i]3. 分组划分类题目会问把若干元素分成几组每组满足某个条件最少分组或最大收益常用技巧枚举 mask 的子集只要题目需要记录“哪些元素已经被使用”就可以优先考虑状态压缩。常见错误点1. 位下标和元素下标混乱第i个元素对应1i不要写成1 (i 1)除非你明确从1开始编号。2. 忘记初始化不可达状态求最小值时不能把所有dp默认成0。应该初始化成较大值Arrays.fill(dp,Integer.MAX_VALUE/2);否则很多不合法状态会被当成合法状态。3. 溢出问题如果用Integer.MAX_VALUE再加一个成本可能溢出。所以常用Integer.MAX_VALUE/24.mask范围写错总状态数是1n循环范围是mask(1n)最终全集是(1n)-15. 没判断当前状态是否合法在dp[mask][i]里要确认(mask(1i))!0否则可能从不存在的状态转移。6. 数据规模太大还硬套状态压缩如果n 30状态数就是2^30这通常已经不可接受。状态压缩 DP 的错误多数来自位运算边界、初始化和状态合法性判断。复杂度分析指数级但可控状态压缩 DP 的复杂度主要看状态数量。dp[mask]类型状态数量是2^n如果每个状态枚举一个元素时间复杂度通常是O(n * 2^n)空间复杂度是O(2^n)dp[mask][i]类型状态数量是n * 2^n如果转移还要枚举下一个点时间复杂度通常是O(n^2 * 2^n)空间复杂度是O(n * 2^n)为什么仍然有价值虽然是指数级但它比暴力排列要好很多。例如访问n个城市的暴力排列复杂度接近O(n!)而状态压缩 DP 可以降到O(n^2 * 2^n)对于小规模n这是非常大的优化。状态压缩 DP 仍然是指数级但通常能把排列级复杂度降到可接受范围。标准思考流程遇到状态压缩题怎么想可以按下面顺序分析。第一步判断是否需要记录集合如果题目要求记录哪些元素用过哪些点访问过哪些任务完成过就可以考虑用mask。第二步确定每一位代表什么写清楚第 i 位表示第 i 个元素是否被选择第三步定义dp常见定义dp[mask] dp[mask][i]第四步确定转移方向通常有两种从旧集合添加一个元素从当前集合删除一个元素初学阶段更推荐“添加元素”的写法。第五步确定初始状态和最终状态常见初始状态dp[0] 0 dp[1 start][start] 0常见最终状态dp[(1 n) - 1] dp[(1 n) - 1][i]状态压缩题先定义每一位的含义再围绕mask设计状态和转移。模板总结状态压缩 DP 怎么写一维集合模板inttotalStates1n;int[]dpnewint[totalStates];Arrays.fill(dp,inf);dp[0]0;for(intmask0;masktotalStates;mask){for(inti0;in;i){if((mask(1i))0){intnextMaskmask|(1i);dp[nextMask]Math.min(dp[nextMask],dp[mask]cost);}}}二维路径模板inttotalStates1n;int[][]dpnewint[totalStates][n];for(int[]row:dp){Arrays.fill(row,inf);}dp[1start][start]0;for(intmask0;masktotalStates;mask){for(inti0;in;i){if((mask(1i))0){continue;}for(intj0;jn;j){if((mask(1j))!0){continue;}intnextMaskmask|(1j);dp[nextMask][j]Math.min(dp[nextMask][j],dp[mask][i]cost);}}}子集枚举模板for(intsubmask;sub0;sub(sub-1)mask){// sub 是 mask 的非空子集}状态压缩 DP 的模板核心就是围绕mask做判断、添加元素和更新状态。总结状态压缩 DP 看起来代码里有很多位运算但本质仍然是动态规划。你可以重点记住下面几句话状态压缩用二进制位表示集合mask是一个整数但可以看作一组选择状态1 i表示第i个元素dp[mask]适合只关心集合本身的问题dp[mask][i]适合既关心集合又关心当前位置的问题总状态数通常是2^n适合小规模问题初始化不可达状态时要用较大值避免非法转移子集枚举可以用(sub - 1) mask状态压缩 DP 的难点不在于背代码而在于先把“每一位表示什么”讲清楚。只要mask的含义稳定转移就会变得有迹可循。