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(List<List<Integer>> arr) { // 帽子颜色的最大值 int m = 0; for (List<Integer> 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-异或运算，题目5，Brian 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 = 0b111，sum = 0：
    • 移除任意一个-5，递归处理0b101或0b110，sum仍为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有效且未被使用，则更新dp：
  • dp[status] = (dp[status] + dp[status ^ cur] * cnt[i]) % MOD
  • 初始化：dp = 2^cnt（数字1可以任意选或不选）。
  • 结果计算：
    • 所有非零状态的dp值之和即为好子集数目。

• 复杂度分析

  • 时间复杂度：O(MAXV * LIMIT)，其中MAXV = 30，LIMIT = 2^10。
  • 空间复杂度：O(LIMIT)，用于存储DP数组。

• 示例

  • 假设nums = [1, 2, 3, 4]：
  • cnt = [0, 1, 1, 1, 1, ...]。
  • own = 0b1，own = 0b10，own = 0（无效）。
  • dp初始为[2, 0, 0, ...]（数字1的贡献）。
  • 处理数字2：
    • dp[0b1] += dp * 1 = 2。
  • 处理数字3：
    • dp[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] 是好子集 // 乘积分别为6=2*3，6=2*3，3=3 // [1, 4]和[4]不是好子集，因为乘积分别为4=2*2和4=2*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个 // 那么认为这个数字无效，状态全是0，0b0000000000 // 如果一个数字拥有任何一种质数因子都不超过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; } }