状 压 DP 前置题目1我能赢吗// 我能赢吗 // 给定两个整数n和m // 两个玩家可以轮流从公共整数池中抽取从1到n的整数不放回 // 抽取的整数会累加起来两个玩家都算 // 谁在自己的回合让累加和 m谁获胜 // 若先出手的玩家能稳赢则返回true否则返回false // 假设两位玩家游戏时都绝顶聪明可以全盘为自己打算 // 测试链接 : https://leetcode.cn/problems/can-i-win/ public class Code01_CanIWin { public static boolean canIWin(int n, int m) { if (m 0) { // 来自题目规定 return true; } if (n * (n 1) / 2 m) { // 如果1~n数字全加起来 // 累加和和是n * (n1) / 2都小于m // 那么不会有赢家也就意味着先手不会获胜 return false; } // dp[status] 0 代表没算过 // dp[status] 1 算过答案是true // dp[status] -1 算过答案是false int[] dp new int[1 (n 1)]; return f(n, (1 (n 1)) - 1, m, dp); } // 如果1~7范围的数字都能选那么status的状态为 // 1 1 1 1 1 1 1 1 // 7 6 5 4 3 2 1 0 // 0位弃而不用 // 如果1~7范围的数字4、2已经选了不能再选那么status的状态为 // 1 1 1 0 1 0 1 1 // 7 6 5 4 3 2 1 0 // 0位弃而不用 // f的含义 : // 数字范围1~n当前的先手面对status给定的数字状态 // 在累加和还剩rest的情况下 // 返回当前的先手能不能赢能赢返回true不能赢返回false public static boolean f(int n, int status, int rest, int[] dp) { if (rest 0) { return false; } if (dp[status] ! 0) { return dp[status] 1; } // rest 0 boolean ans false; for (int i 1; i n; i) { // 考察所有数字但是不能选择之前选了的数字 if ((status (1 i)) ! 0 !f(n, (status ^ (1 i)), rest - i, dp)) { ans true; break; } } dp[status] ans ? 1 : -1; return ans; } }// f的含义 :// 数字范围1~n当前的先手面对status给定的数字状态// 在累加和还剩rest的情况下// 返回当前的先手能不能赢能赢返回true不能赢返回false题目2火柴拼正方形public class Code02_MatchsticksToSquare { public static boolean makesquare(int[] nums) { int sum 0; for (int num : nums) { sum num; } if (sum % 4 ! 0) { return false; } int n nums.length; int[] dp new int[1 n]; return f(nums, sum / 4, (1 n) - 1, 0, 4, dp); } // limit : 每条边规定的长度 // status : 表示哪些数字还可以选 // cur : 当前要解决的这条边已经形成的长度 // rest : 一共还有几条边没有解决 // 返回 : 能否用光所有火柴去解决剩下的所有边 // 因为调用子过程之前一定保证每条边累加起来都不超过limit // 所以status是决定cur和rest的关键可变参数只有status public static boolean f(int[] nums, int limit, int status, int cur, int rest, int[] dp) { if (rest 0) { return status 0; } if (dp[status] ! 0) { return dp[status] 1; } boolean ans false; for (int i 0; i nums.length; i) { // 考察每一根火柴只能使用状态为1的火柴 if ((status (1 i)) ! 0 cur nums[i] limit) { if (cur nums[i] limit) { ans f(nums, limit, status ^ (1 i), 0, rest - 1, dp); } else { ans f(nums, limit, status ^ (1 i), cur nums[i], rest, dp); } if (ans) { break; } } } dp[status] ans ? 1 : -1; return ans; } }题目3划分k个相等的子集public class Solution { // 状压dp的解法 // 这是最正式的解 public static boolean canPartitionKSubsets(int[] nums, int k) { int sum 0; for (int num : nums) { sum num; } if (sum % k ! 0) { return false; } int n nums.length; int[] dp new int[1 n]; return f1(nums, sum / k, (1 n) - 1, 0, k, dp); } // 就是题目2的递归函数 public static boolean f1(int[] nums, int limit, int status, int cur, int rest, int[] dp) { if (rest 0) { return status 0; } if (dp[status] ! 0) { return dp[status] 1; } boolean ans false; for (int i 0; i nums.length; i) { if ((status (1 i)) ! 0 cur nums[i] limit) { if (cur nums[i] limit) { ans f1(nums, limit, status ^ (1 i), 0, rest - 1, dp); } else { ans f1(nums, limit, status ^ (1 i), cur nums[i], rest, dp); } if (ans) { break; } } } dp[status] ans ? 1 : -1; return ans; } // 纯暴力的递归不做任何动态规划利用良好的剪枝策略可以做到非常好的效率 // 但这并不是正式的解如果数据设计的很苛刻是通过不了的 public static boolean canPartitionKSubsets2(int[] nums, int k) { int sum 0; for (int num : nums) { sum num; } if (sum % k ! 0) { return false; } int n nums.length; Arrays.sort(nums); return f2(new int[k], sum / k, nums, n - 1); } // group里面是各个集合已经有的累加和 // 随着递归的展开group里的累加和会变化 // 所以这是一个带路径的递归而且路径信息比较复杂(group数组) // 无法改成动态规划但是利用剪枝策略可以通过 // group[0....index]这些数字填入每个集合一定要都使用 // 每个集合的累加和一定都要是target返回能不能做到 public static boolean f2(int[] group, int target, int[] nums, int index) { if (index 0) { return true; } int num nums[index]; int len group.length; for (int i 0; i len; i) { if (group[i] num target) { // 当前数字num放进i号集合 group[i] num; if (f2(group, target, nums, index - 1)) { return true; } // 递归完成后将路径还原 group[i] - num; while (i 1 group.length group[i] group[i 1]) { i; } } } return false; } }题目4售货员的难题import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; // 正常来说把MAXN改成20能通过实现是正确的 // 问题是卡空间而且c的实现不卡空间就卡java的实现 // 但如果把MAXN改成19会有一个测试用例通过不了 // 那就差这么一点空间...看不起java是吗 // 好你歧视java实现那就别怪我了 // 完全能通过的版本看Code04_TSP2的实现 public class Main { public static int MAXN 19; public static int[][] graph new int[MAXN][MAXN]; public static int[][] dp new int[1 MAXN][MAXN]; public static int n; public static void build() { for (int s 0; s (1 n); s) { for (int i 0; i n; i) { dp[s][i] -1; } } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer in new StreamTokenizer(br); PrintWriter out new PrintWriter(new OutputStreamWriter(System.out)); while (in.nextToken() ! StreamTokenizer.TT_EOF) { n (int) in.nval; build(); for (int i 0; i n; i) { for (int j 0; j n; j) { in.nextToken(); graph[i][j] (int) in.nval; } } out.println(compute()); } out.flush(); out.close(); br.close(); } public static int compute() { return f(1, 0); } // s : 村里走没走过的状态1走过了不要再走了0可以走 // i : 目前在哪个村 public static int f(int s, int i) { if (s (1 n) - 1) { // n : 000011111 return graph[i][0]; } if (dp[s][i] ! -1) { return dp[s][i]; } int ans Integer.MAX_VALUE; for (int j 0; j n; j) { // 0...n-1这些村都看看是不是下一个落脚点 if ((s (1 j)) 0) { ans Math.min(ans, graph[i][j] f(s | (1 j), j)); } } dp[s][i] ans; return ans; } }题目51434. 每个人戴不同帽子的方案数 - 力扣LeetCode// 每个人戴不同帽子的方案数 // 总共有 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; } }题目61994. 好子集的数目 - 力扣LeetCodepublic class Solution { 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 numberOfGoodSubsets(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; } }题目71655. 分配重复整数 - 力扣LeetCodepublic class Solution { // 时间复杂度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; } }