80.【必备】状压dp-下

本文的网课内容学习自B站左程云老师的算法详解课程旨在对其中的知识进行整理和分享~网课链接算法讲解081【必备】状压dp-下_哔哩哔哩_bilibili一.每个人戴不同帽子的方案数题目每个人戴不同帽子的方案数算法原理整体原理该问题要求为n个人分配他们喜欢的帽子确保每个人戴的帽子不同计算所有可能的分配方案数。由于帽子数量较多最多40种直接暴力枚举不可行因此采用状态压缩动态规划来高效计算。具体步骤问题建模将每个人喜欢的帽子列表转换为位掩码形式hats[hat]表示喜欢该帽子的人的集合位掩码。使用动态规划表dp[i][s]表示处理到第i种帽子时当前已分配帽子的人的状态为s时的方案数。状态压缩动态规划状态定义dp[i][s]表示处理前i种帽子已分配帽子的人的状态为s时的方案数。初始化dp初始化为-1表示未计算。转移方程若所有人已分配帽子s (1 n) - 1返回1。若所有帽子处理完毕但未分配完所有人i m 1返回0。对于当前帽子i有两种选择不分配该帽子f(hats, m, n, i 1, s, dp)。分配该帽子给喜欢它且未分配帽子的人遍历所有可能的人更新状态s | (1 p)并累加方案数。记忆化缓存已计算的状态避免重复计算。优化使用Brian Kernighan算法高效遍历位掩码中的1减少不必要的循环。复杂度分析时间复杂度O(m * 2^n * k)其中m为帽子数量n为人数k为平均每顶帽子喜欢的人数。空间复杂度O(m * 2^n)用于存储DP表。示例假设有2个人和3顶帽子hats [[1,2], [2,3]]。hats 0b01第0人喜欢hats 0b11第0和1人喜欢hats 0b10第1人喜欢。计算过程初始状态s 0从帽子1开始不分配帽子1递归处理帽子2。分配帽子1给第0人s 0b01递归处理帽子2。处理帽子2时不分配帽子2递归处理帽子3。分配帽子2给第0人已被分配跳过或第1人s 0b11返回1。最终方案数为2分配顺序1→2或2→3。总结状态压缩动态规划高效处理组合问题适用于小规模数据。位运算优化Brian Kernighan算法提升遍历效率。适用性适用于人数较少n ≤ 20的场景确保时间和空间复杂度可行。代码实现import java.util.Arrays; import java.util.List; // 每个人戴不同帽子的方案数 // 总共有 n 个人和 40 种不同的帽子帽子编号从 1 到 40 // 给你一个整数列表的列表 hats 其中 hats[i] 是第 i 个人所有喜欢帽子的列表 // 请你给每个人安排一顶他喜欢的帽子确保每个人戴的帽子跟别人都不一样并返回方案数 // 由于答案可能很大答案对 1000000007 取模 // 测试链接 : https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other public class Code01_NumberOfWaysWearDifferentHats { public static int MOD 1000000007; public static int numberWays(ListListInteger arr) { // 帽子颜色的最大值 int m 0; for (ListInteger person : arr) { for (int hat : person) { m Math.max(m, hat); } } int n arr.size(); // 1 ~ m 帽子能满足哪些人状态信息 - int int[] hats new int[m 1]; for (int pi 0; pi n; pi) { for (int hat : arr.get(pi)) { hats[hat] | 1 pi; } } int[][] dp new int[m 1][1 n]; for (int i 0; i m; i) { Arrays.fill(dp[i], -1); } return f2(hats, m, n, 1, 0, dp); } // m : 帽子颜色的最大值, 1 ~ m // n : 人的数量0 ~ n-1 // i : 来到了什么颜色的帽子 // s : n个人谁没满足状态就是0谁满足了状态就是1 // dp : 记忆化搜索的表 // 返回 : 有多少种方法 public static int f1(int[] hats, int m, int n, int i, int s, int[][] dp) { if (s (1 n) - 1) { return 1; } // 还有人没满足 if (i m 1) { return 0; } if (dp[i][s] ! -1) { return dp[i][s]; } // 可能性1 : i颜色的帽子不分配给任何人 int ans f1(hats, m, n, i 1, s, dp); // 可能性2 : i颜色的帽子分配给可能的每一个人 int cur hats[i]; // 用for循环从0 ~ n-1枚举每个人 for (int p 0; p n; p) { if ((cur (1 p)) ! 0 (s (1 p)) 0) { ans (ans f1(hats, m, n, i 1, s | (1 p), dp)) % MOD; } } dp[i][s] ans; return ans; } public static int f2(int[] hats, int m, int n, int i, int s, int[][] dp) { if (s (1 n) - 1) { return 1; } if (i m 1) { return 0; } if (dp[i][s] ! -1) { return dp[i][s]; } int ans f2(hats, m, n, i 1, s, dp); int cur hats[i]; // 不用for循环枚举 // 从当前帽子中依次提取能满足的人 // 提取出二进制状态中最右侧的1讲解030-异或运算题目5Brian Kernighan算法 // cur : // 0 0 0 1 1 0 1 0 // - 0 0 0 0 0 0 1 0 // - 0 0 0 0 1 0 0 0 // - 0 0 0 1 0 0 0 0 int rightOne; while (cur ! 0) { rightOne cur -cur; if ((s rightOne) 0) { ans (ans f2(hats, m, n, i 1, s | rightOne, dp)) % MOD; } cur ^ rightOne; } dp[i][s] ans; return ans; } }二.最优账单平衡题目最优账单平衡算法原理整体原理该问题要求通过最少的交易笔数使得所有人的债务清零。关键在于将债务处理转化为集合划分问题利用状态压缩动态规划高效求解。具体步骤债务计算统计每个人的净债务debt数组过滤掉净债务为0的人。净债务为正表示应收款为负表示应付款。状态压缩动态规划状态定义dp[set]表示处理集合set中的债务时可以形成的最大零和子集数量。转移方程若集合中不只一个元素若当前子集和为零sum 0则选择一个元素移除递归处理剩余集合结果加1。否则尝试移除每个元素递归处理剩余集合取最大值。记忆化缓存已计算的状态避免重复计算。最小交易笔数总人数减去最大零和子集数量即为最小交易笔数。复杂度分析时间复杂度O(3^n)其中n为债务人数最多12人。空间复杂度O(2^n)用于存储DP表。示例假设债务数组为[10, -5, -5]初始集合set 0b111sum 0移除任意一个-5递归处理0b101或0b110sum仍为0。最终形成两个零和子集[10, -5, -5]和最大零和子集数量为2。最小交易笔数为3 - 2 1一笔交易10 → 5和5。总结状态压缩动态规划高效处理集合划分问题。零和子集通过寻找零和子集减少交易笔数。适用性适用于债务人数较少n ≤ 12的场景。代码实现import java.util.Arrays; // 最优账单平衡 // 给你一个表示交易的数组 transactions // 其中 transactions[i] [fromi, toi, amounti] // 表示 ID fromi 的人给 ID toi 的人共计 amounti // 请你计算并返回还清所有债务的最小交易笔数 // 测试链接 : https://leetcode.cn/problems/optimal-account-balancing/ public class Code02_OptimalAccountBalancing { // 题目说了人员编号的最大范围0 ~ 12 public static int MAXN 13; public static int minTransfers(int[][] transactions) { // 加工出来的debt数组中一定不含有0 int[] debt debts(transactions); int n debt.length; int[] dp new int[1 n]; Arrays.fill(dp, -1); return n - f(debt, (1 n) - 1, 0, n, dp); } public static int[] debts(int[][] transactions) { int[] help new int[MAXN]; for (int[] tran : transactions) { help[tran[0]] - tran[2]; help[tran[1]] tran[2]; } int n 0; for (int num : help) { if (num ! 0) { n; } } int[] debt new int[n]; int index 0; for (int num : help) { if (num ! 0) { debt[index] num; } } return debt; } public static int f(int[] debt, int set, int sum, int n, int[] dp) { if (dp[set] ! -1) { return dp[set]; } int ans 0; if ((set (set - 1)) ! 0) { // 集合中不只一个元素 if (sum 0) { for (int i 0; i n; i) { if ((set (1 i)) ! 0) { // 找到任何一个元素去除这个元素 // 剩下的集合进行尝试返回值 1 ans f(debt, set ^ (1 i), sum - debt[i], n, dp) 1; // 然后不需要再尝试下一个元素了因为答案一定是一样的 // 所以直接break break; } } } else { for (int i 0; i n; i) { if ((set (1 i)) ! 0) { ans Math.max(ans, f(debt, set ^ (1 i), sum - debt[i], n, dp)); } } } } dp[set] ans; return ans; } }三.好子集的数目题目好子集的数目算法原理整体原理该问题要求统计数组中所有子集的乘积可以表示为互不相同质数乘积的子集数目。关键在于将数字的质因数分解转化为状态压缩利用动态规划高效计算。具体步骤预处理统计每个数字的出现次数cnt数组。预处理每个数字的质因数状态own数组用位掩码表示其包含的质数。状态压缩动态规划状态定义dp[status]表示当前质因数状态为status的子集数目。转移方程对于每个数字i若其质因数状态cur有效且未被使用则更新dpdp[status] (dp[status] dp[status ^ cur] * cnt[i]) % MOD初始化dp 2^cnt数字1可以任意选或不选。结果计算所有非零状态的dp值之和即为好子集数目。复杂度分析时间复杂度O(MAXV * LIMIT)其中MAXV 30LIMIT 2^10。空间复杂度O(LIMIT)用于存储DP数组。示例假设nums [1, 2, 3, 4]cnt [0, 1, 1, 1, 1, ...]。own 0b1own 0b10own 0无效。dp初始为[2, 0, 0, ...]数字1的贡献。处理数字2dp[0b1] dp * 1 2。处理数字3dp[0b10] dp * 1 2。dp[0b11] dp[0b01] * 1 2。结果dp dp dp 2 2 2 6对应子集, , [1,2], [1,3], [2,3], [1,2,3]。总结状态压缩将质因数状态压缩为位掩码高效处理子集问题。动态规划通过状态转移累计有效子集数目。适用性适用于数字范围较小≤30的场景。代码实现import java.util.Arrays; // 好子集的数目 // 给你一个整数数组 nums好子集的定义如下 // nums的某个子集所有元素的乘积可以表示为一个或多个互不相同质数的乘积 // 比如nums [1, 2, 3, 4] // [2, 3][1, 2, 3][1, 3] 是好子集 // 乘积分别为62*362*333 // [1, 4]和[4]不是好子集因为乘积分别为42*2和42*2 // 返回nums中不同的好子集的数目答案对 1000000007 取模 // 如果两个子集删除的下标不同那么它们被视为不同的子集 // 测试链接 : https://leetcode.cn/problems/the-number-of-good-subsets/ public class Code03_TheNumberOfGoodSubsets { public static int MAXV 30; public static int LIMIT (1 10); public static int MOD 1000000007; // 打个表来加速判断 // 如果一个数字拥有某一种质数因子不只1个 // 那么认为这个数字无效状态全是00b0000000000 // 如果一个数字拥有任何一种质数因子都不超过1个 // 那么认为这个数字有效用位信息表示这个数字拥有质数因子的状态 // 比如12拥有2这种质数因子不只1个所以无效用0b0000000000表示 // 比如14拥有2这种质数因子不超过1个拥有7这种质数因子不超过1个有效 // 从高位到低位依次表示...13 11 7 5 3 2 // 所以用0b0000001001表示14拥有质数因子的状态 // 质数: 29 23 19 17 13 11 7 5 3 2 // 位置: 9 8 7 6 5 4 3 2 1 0 public static int[] own { 0b0000000000, // 0 0b0000000000, // 1 0b0000000001, // 2 0b0000000010, // 3 0b0000000000, // 4 0b0000000100, // 5 0b0000000011, // 6 0b0000001000, // 7 0b0000000000, // 8 0b0000000000, // 9 0b0000000101, // 10 0b0000010000, // 11 0b0000000000, // 12 0b0000100000, // 13 0b0000001001, // 14 0b0000000110, // 15 0b0000000000, // 16 0b0001000000, // 17 0b0000000000, // 18 0b0010000000, // 19 0b0000000000, // 20 0b0000001010, // 21 0b0000010001, // 22 0b0100000000, // 23 0b0000000000, // 24 0b0000000000, // 25 0b0000100001, // 26 0b0000000000, // 27 0b0000000000, // 28 0b1000000000, // 29 0b0000000111 // 30 }; // 记忆化搜索 public static int numberOfGoodSubsets1(int[] nums) { // 1 ~ 30 int[] cnt new int[MAXV 1]; for (int num : nums) { cnt[num]; } int[][] dp new int[MAXV 1][LIMIT]; for (int i 0; i MAXV; i) { Arrays.fill(dp[i], -1); } int ans 0; for (int s 1; s LIMIT; s) { ans (ans f1(MAXV, s, cnt, dp)) % MOD; } return ans; } // 1....i范围的数字每种数字cnt[i]个 // 最终相乘的结果一定要让质因子的状态为s且每种质因子只能有1个 // 请问子集的数量是多少 // s每一位代表的质因子如下 // 质数: 29 23 19 17 13 11 7 5 3 2 // 位置: 9 8 7 6 5 4 3 2 1 0 public static int f1(int i, int s, int[] cnt, int[][] dp) { if (dp[i][s] ! -1) { return dp[i][s]; } int ans 0; if (i 1) { if (s 0) { ans 1; for (int j 0; j cnt[1]; j) { ans (ans 1) % MOD; } } } else { ans f1(i - 1, s, cnt, dp); int cur own[i]; int times cnt[i]; if (cur ! 0 times ! 0 (s cur) cur) { // 能要i这个数字 ans (int) (((long) f1(i - 1, s ^ cur, cnt, dp) * times ans) % MOD); } } dp[i][s] ans; return ans; } // 空间压缩优化 public static int[] cnt new int[MAXV 1]; public static int[] dp new int[LIMIT]; public static int numberOfGoodSubsets2(int[] nums) { Arrays.fill(cnt, 0); Arrays.fill(dp, 0); for (int num : nums) { cnt[num]; } dp[0] 1; for (int i 0; i cnt[1]; i) { dp[0] (dp[0] 1) % MOD; } for (int i 2, cur, times; i MAXV; i) { cur own[i]; times cnt[i]; if (cur ! 0 times ! 0) { for (int status LIMIT - 1; status 0; status--) { if ((status cur) cur) { dp[status] (int) (((long) dp[status ^ cur] * times dp[status]) % MOD); } } } } int ans 0; for (int s 1; s LIMIT; s) { ans (ans dp[s]) % MOD; } return ans; } }四.分配重复整数题目分配重复整数算法原理整体原理该问题要求判断是否可以将数组中的整数分配给多个顾客满足每个顾客的需求特定数量的相同整数。通过统计数字频率和顾客需求利用状态压缩动态规划高效求解。具体步骤预处理统计每个数字的出现次数cnt数组。计算每个顾客需求的子集和sum数组用于快速判断某个子集需求的总和。状态压缩动态规划状态定义dp[status][index]表示处理到第index个数字时订单状态为status位掩码是否可满足。转移方程对于当前数字cnt[index]枚举所有未满足的订单子集j若子集需求总和sum[j]不超过当前数字数量k则递归处理剩余订单状态status ^ j和下一个数字。若无法满足任何子集则跳过当前数字递归处理下一个数字。记忆化缓存已计算的状态避免重复计算。结果判断初始状态为所有订单未满足status (1 m) - 1从第一个数字开始递归最终返回是否满足所有订单。复杂度分析时间复杂度O(n * 3^m)其中n为数字种类数m为顾客数。每个状态需要枚举所有子集。空间复杂度O(n * 2^m)用于存储DP表。示例假设nums [1, 2, 2, 3]quantity [2, 2]cnt [1, 2, 1]数字1、2、3的频率。sum [0, 2, 2, 4]子集需求总和。初始状态status 0b11两个订单未满足尝试用数字2频率2满足第一个订单需求2剩余状态0b10递归处理。用数字2频率2满足第二个订单需求2剩余状态0b00返回true。总结状态压缩将订单状态压缩为位掩码高效处理子集需求。动态规划通过递归和记忆化搜索逐步满足订单需求。适用性适用于顾客数较少m ≤ 20的场景确保时间复杂度可行。代码实现import java.util.Arrays; // 分配重复整数 // 给你一个长度为n的整数数组nums这个数组中至多有50个不同的值 // 同时你有m个顾客的订单quantity其中整数quantity[i]是第i位顾客订单的数目 // 请你判断是否能将nums中的整数分配给这些顾客且满足 // 第i位顾客恰好有quantity[i]个整数、第i位顾客拿到的整数都是相同的 // 每位顾客都要满足上述两个要求返回是否能都满足 // 测试链接 : https://leetcode.cn/problems/distribute-repeating-integers/ public class Code04_DistributeRepeatingIntegers { // 时间复杂度O(n * 3的m次方)空间复杂度O(n * 2的m次方) // ppt上有时间复杂度解析 public static boolean canDistribute(int[] nums, int[] quantity) { Arrays.sort(nums); int n 1; for (int i 1; i nums.length; i) { if (nums[i - 1] ! nums[i]) { n; } } int[] cnt new int[n]; int c 1; for (int i 1, j 0; i nums.length; i) { if (nums[i - 1] ! nums[i]) { cnt[j] c; c 1; } else { c; } } cnt[n - 1] c; int m quantity.length; int[] sum new int[1 m]; // 下面这个枚举是生成quantity中的每个子集所需要数字的个数 for (int i 0, v, h; i quantity.length; i) { v quantity[i]; h 1 i; for (int j 0; j h; j) { sum[h | j] sum[j] v; } } int[][] dp new int[1 m][n]; return f(cnt, sum, (1 m) - 1, 0, dp); } // 当前来到的数字编号index个数cnt[index] // status : 订单状态1还需要去满足0已经满足过了 public static boolean f(int[] cnt, int[] sum, int status, int index, int[][] dp) { if (status 0) { return true; } // status ! 0 if (index cnt.length) { return false; } if (dp[status][index] ! 0) { return dp[status][index] 1; } boolean ans false; int k cnt[index]; // 这是整个实现最核心的枚举 // j枚举了status的所有子集状态 // 建议记住 for (int j status; j 0; j (j - 1) status) { if (sum[j] k f(cnt, sum, status ^ j, index 1, dp)) { ans true; break; } } if (!ans) { ans f(cnt, sum, status, index 1, dp); } dp[status][index] ans ? 1 : -1; return ans; } }