科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文围绕 LeetCode 996 号问题「漂亮的排列」Number of Squareful Arrays展开系统讲解如何用状压 DP求解相邻两数之和为完全平方数的排列计数问题。全文以 996.md 题解为骨架完整覆盖寻找子问题 → 状态定义与转移方程 → 记忆化搜索 → 去重 → 1:1 翻译成递推的完整推导链路并结合 codeforces-go 仓库中 d.go 的源码实现与 d_test.go 的测试验证帮助读者掌握排列型状压 DP 的通用套路状态压缩表示集合、枚举子集做转移、重复元素去重以及记忆化搜索与递推两种写法的等价转换。题目核心问题给定一个整数数组nums如果一个排列中任意相邻两个数之和都是完全平方数则称该排列为漂亮排列要求统计满足条件的不同排列的数量。从仓库测试文件 d_test.go 中的题目链接注释可以看到本题正是https://leetcode.cn/problems/number-of-squareful-arrays/第 124 场周赛的最后一题对应函数签名func numSquarefulPerms(nums []int) int。测试数据 d.txt 给出了两个关键样例[1,17,8] 2 [2,2,2] 1第一个样例说明189、81725都是完全平方数唯一合法排列是[1,8,17]与[17,8,1]共 2 个第二个样例说明[2,2,2]中所有相邻之和都是 4完全平方数但由于三个 2 完全相同只能算 1 种不同排列——这直接引出了本文的重点之一去重。前置知识本题解法依赖两项基础技能状压 DP 的方法论从记忆化搜索到递推的 1:1 翻译技巧状态定义不变只改计算顺序。从集合论到位运算用二进制整数表示集合用位运算实现判断元素是否在集合中从集合中删除元素枚举集合中的元素等操作。仓库中 bits.go 对这类位运算基础做了集中说明并指出二进制枚举、枚举子集的子集、枚举大小固定集合等写法统一整理在 search.go 中可作为阅读本文时随时查阅的位运算速查手册。一、寻找子问题把大排列拆成小排列以示例nums[1,17,8]为例。枚举排列的第一个数第一个数是1问题变成在前一个数是 1 的情况下剩余的{17,8}能组成多少个合法排列若第二个数是8问题进一步变成在前一个数是 8 的情况下剩余的{17}能组成多少个合法排列。第一个数是17问题变成在前一个数是 17 的情况下剩余的{1,8}能组成多少个合法排列。第一个数是8问题变成在前一个数是 8 的情况下剩余的{1,17}能组成多少个合法排列。这些子问题与原始问题同构且规模更小天然适合用递归深度优先搜索解决。关键观察是决定未来可行性的信息只有两个——还剩哪些数可选、上一个填入的数是什么。至于排列的前半段具体长什么样与后续选择无关无后效性这正是 DP 成立的前提。二、状态定义与状态转移方程递归时需要跟踪两件事当前还剩下哪些数可以选。由于nums[i]的值域很大不方便直接用数值本身做状态更好的方式是跟踪剩余可选的下标集合用二进制整数表示上一个填入的数的下标。由此定义dfs(S, i)表示在剩余可选下标集合为S、上一个数的下标为i的情况下剩余元素可以组成多少个合法排列。枚举S中的下标j若nums[i] nums[j]是完全平方数就可以把nums[j]填入当前位问题缩小为dfs(S \ {j}, j)。累加所有合法选择得到状态转移方程$$ dfs(S,i) \sum_{j} dfs(S\setminus{j},j) $$其中 $j \in S$ 且 $\textit{nums}[i]\textit{nums}[j]$ 是完全平方数。递归边界dfs(∅) 1。能递归到S ∅说明所有数都已选完且任意相邻之和都是完全平方数即找到了一个合法排列。更严谨的写法是dfs(∅, i) 1集合为空时上一个数的下标不再影响结果。递归入口枚举排列第一个数的下标i 0, 1, ..., n-1问题变成dfs(U \ {i}, i)其中全集U {0, 1, ..., n-1}。如果nums没有重复元素答案就是$$ A \sum_{i0}^{n-1} dfs(U\setminus{i}, i) $$重复元素去重除以出现次数阶乘的乘积本题的nums可能存在重复元素。例如nums [1,8,1,8,1]对于任意合法排列P3 个 1 内部互换可以得到3! 6个完全一样的排列2 个 8 内部互换可以得到2! 2个完全一样的排列。由于两种互换相互独立根据乘法原理会统计出3!·2! 12个彼此重复的P。一般化的处理统计nums中每个元素的出现次数把A除以所有出现次数的阶乘的乘积即得到去重后的答案。代码实现时有一个省事的技巧不显式计算阶乘而是顺序遍历每个元素执行ans / cnt[x]。若某元素出现 3 次则依次除以 1、2、3等效于除以3!。仓库 Go 实现 d.go 正是这样写的// 去重 cnt : map[int]int{} for _, x : range nums { cnt[x] ans / cnt[x] // 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) }三、递归搜索 保存返回值 记忆化搜索递归过程中存在大量入参相同的重复调用。由于递归函数没有副作用同样的入参无论计算多少次结果都一样因此可以用记忆化消除重复计算第一次遇到某个状态递归入参时在返回前把状态 → 结果记录到memo数组中之后再次遇到该状态时直接返回memo中保存的结果。⚠注意memo数组的初始值绝对不能等于要记忆化的值。例如初始值设为 0而某个dfs(S, i)的结果恰好也是 0就无法区分这个状态还没算过和这个状态算过且结果为 0记忆化将失效。惯例是把初始值设为-1合法结果非负。Python 用户可直接用cache装饰器一行代码免去手动初始化。在代码实现中用二进制整数表示集合S配套的位运算写法详见 search.go 与 bits.go全集u (1 n) - 1即二进制低 n 位全为 1判断j是否在s中sj1 0从s中删除js ^ (1j)因为j在s中异或等价于把该位清零。记忆化搜索实现四语言对照Python3class Solution: def numSquarefulPerms(self, nums: list[int]) - int: # 判断 x 是否为完全平方数 def is_square(x: int) - bool: rt isqrt(x) return rt * rt x n len(nums) # s 表示剩余可选元素的下标集合 # i 表示上一个数我们刚刚填入的数的下标 cache # 缓存装饰器避免重复计算 dfs一行代码实现记忆化 def dfs(s: int, i: int) - int: if s 0: # 填完了 return 1 # 找到一个合法排列 res 0 # 枚举当前位置填 nums[j] for j in range(n): # (sj1)1 表示 j 在 s 中 if s j 1 and is_square(nums[i] nums[j]): res dfs(s ^ (1 j), j) # 从 s 中去掉 j return res ans 0 # 枚举排列的第一个数的下标 u (1 n) - 1 # 全集 u {0,1,2,...,n-1} for i in range(n): ans dfs(u ^ (1 i), i) # 从 u 中去掉 i # 去重 cnt defaultdict(int) for x in nums: cnt[x] 1 ans // cnt[x] # 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) return ansJavaclass Solution { public int numSquarefulPerms(int[] nums) { int n nums.length; int[][] memo new int[1 n][n]; for (int[] row : memo) { Arrays.fill(row, -1); // -1 表示没有计算过 } int ans 0; // 枚举排列的第一个数的下标 int u (1 n) - 1; // 全集 u {0,1,2,...,n-1} for (int i 0; i n; i) { ans dfs(u ^ (1 i), i, nums, memo); // 从 u 中去掉 i } // 去重 MapInteger, Integer cnt new HashMap(); for (int x : nums) { int c cnt.merge(x, 1, Integer::sum); // c cnt[x] ans / c; // 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) } return ans; } // s 表示剩余可选元素的下标集合 // i 表示上一个数我们刚刚填入的数的下标 private int dfs(int s, int i, int[] nums, int[][] memo) { if (s 0) { // 填完了 return 1; // 找到一个合法排列 } if (memo[s][i] ! -1) { // 之前计算过 return memo[s][i]; } int res 0; // 枚举当前位置填 nums[j] for (int j 0; j nums.length; j) { // (sj1)0 表示 j 在 s 中 if ((s j 1) 0 isSquare(nums[i] nums[j])) { res dfs(s ^ (1 j), j, nums, memo); // 从 s 中去掉 j } } memo[s][i] res; // 记忆化 return res; } // 判断 x 是否为完全平方数 private boolean isSquare(int x) { int rt (int) Math.sqrt(x); return rt * rt x; } }Cclass Solution { // 判断 x 是否为完全平方数 bool is_square(int x) { int rt sqrt(x); return rt * rt x; } public: int numSquarefulPerms(vectorint nums) { int n nums.size(); vector memo(1 n, vectorint(n, -1)); // -1 表示没有计算过 // s 表示剩余可选元素的下标集合 // i 表示上一个数我们刚刚填入的数的下标 auto dfs - int { if (s 0) { // 填完了 return 1; // 找到一个合法排列 } int res memo[s][i]; // 注意这里是引用 if (res ! -1) { // 之前计算过 return res; } res 0; // 枚举当前位置填 nums[j] for (int j 0; j n; j) { // (sj1)1 表示 j 在 s 中 if (s j 1 is_square(nums[i] nums[j])) { res dfs(s ^ (1 j), j); // 从 s 中去掉 j } } return res; }; int ans 0; // 枚举排列的第一个数的下标 int u (1 n) - 1; // 全集 u {0,1,2,...,n-1} for (int i 0; i n; i) { ans dfs(u ^ (1 i), i); // 从 u 中去掉 i } // 去重 unordered_mapint, int cnt; for (int x : nums) { ans / cnt[x]; // 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) } return ans; } };Go与仓库实现同源// 判断 x 是否为完全平方数 func isSquare(x int) bool { rt : int(math.Sqrt(float64(x))) return rt*rt x } func numSquarefulPerms(nums []int) (ans int) { n : len(nums) memo : make([][]int, 1n) for i : range memo { memo[i] make([]int, n) for j : range memo[i] { memo[i][j] -1 // -1 表示没有计算过 } } // s 表示剩余可选元素的下标集合 // i 表示上一个数我们刚刚填入的数的下标 var dfs func(int, int) int dfs func(s, i int) (res int) { if s 0 { // 填完了 return 1 // 找到一个合法排列 } p : memo[s][i] if *p ! -1 { // 之前计算过 return *p } // 枚举当前位置填 nums[j] for j : range n { // sj1 0 表示 j 在 s 中 if sj1 0 isSquare(nums[i]nums[j]) { res dfs(s^1j, j) // 从 s 中去掉 j } } *p res // 记忆化 return } // 枚举排列的第一个数的下标 u : 1n - 1 // 全集 u {0,1,2,...,n-1} for i : range n { ans dfs(u^1i, i) // 从 u 中去掉 i } // 去重 cnt : map[int]int{} for _, x : range nums { cnt[x] ans / cnt[x] // 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) } return }关于 Go 代码中s^1j的写法bits.go 给出了 Go 运算符优先级的权威说明* / % ^的优先级5高于 - | ^4因此s ^ 1 j等价于s ^ (1 j)即从s中移除j写法符合 Go 语言规范。复杂度分析记忆化搜索版时间复杂度O(n²·2ⁿ)其中 n 是nums的长度。动态规划的时间复杂度 状态个数 × 单个状态的计算时间。状态个数为 O(n·2ⁿ)集合状态 2ⁿ 个乘以上一个数的下标 n 种单个状态内枚举 n 个候选并做常数时间的完全平方数判断故总复杂度为 O(n²·2ⁿ)。空间复杂度O(n·2ⁿ)即保存memo数组所需的存储。由于状态数是 2ⁿ 的规模这类做法适用于 n 较小的场景本题数据规模下完全可行当 n 较大时则需要借助枚举子集的子集等位运算优化技巧仓库 search.go 中提供了sub (sub-1) set枚举子集、按固定大小枚举子集等模板。四、1:1 翻译成递推自底向上记忆化搜索的本质是递归 缓存其计算顺序由递归自然决定。我们完全可以去掉递归中的递自上而下的展开只保留归的部分自底向上的合并即递推。定义f[S][i]与dfs(S, i)完全一致表示在剩余可选下标集合为S、上一个数的下标为i的情况下剩余元素能组成多少个合法排列。转移方程同构$$ f[S][i] \sum_{j} f[S\setminus{j}][j] $$其中 $j \in S$ 且 $\textit{nums}[i]\textit{nums}[j]$ 是完全平方数。初始值f[∅] 1即f[0][i] 1对所有 i翻译自递归边界dfs(∅) 1。递推完毕后计算$$ A \sum_{i0}^{n-1} f[U\setminus{i}][i] $$最后同样统计每个元素的出现次数把A除以出现次数阶乘的乘积即为最终答案。一个值得注意的实现细节递推循环中i必须是不在s中的下标因为i代表已经填过的数不可能留在剩余集合里代码通过if si1 0 { continue }跳过非法状态。递推实现四语言对照Python3class Solution: def numSquarefulPerms(self, nums: list[int]) - int: # 判断 x 是否为完全平方数 def is_square(x: int) - bool: rt isqrt(x) return rt * rt x n len(nums) f [[0] * n for _ in range(1 n)] f[0] [1] * n u (1 n) - 1 for s in range(1, u): for i in range(n): if s i 1: # i 是填过的数的下标不能在 s 中 continue for j in range(n): if s j 1 and is_square(nums[i] nums[j]): f[s][i] f[s ^ (1 j)][j] ans 0 # 枚举排列的第一个数的下标 for i in range(n): ans f[u ^ (1 i)][i] # 去重 cnt defaultdict(int) for x in nums: cnt[x] 1 ans // cnt[x] # 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) return ansJavaclass Solution { public int numSquarefulPerms(int[] nums) { int n nums.length; int[][] f new int[1 n][n]; Arrays.fill(f[0], 1); int u (1 n) - 1; for (int s 1; s u; s) { for (int i 0; i n; i) { if ((s i 1) 0) { // i 是填过的数的下标不能在 s 中 continue; } for (int j 0; j n; j) { if ((s j 1) 0 isSquare(nums[i] nums[j])) { f[s][i] f[s ^ (1 j)][j]; } } } } int ans 0; // 枚举排列的第一个数的下标 for (int i 0; i n; i) { ans f[u ^ (1 i)][i]; } // 去重 MapInteger, Integer cnt new HashMap(); for (int x : nums) { int c cnt.merge(x, 1, Integer::sum); // c cnt[x] ans / c; // 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) } return ans; } // 判断 x 是否为完全平方数 private boolean isSquare(int x) { int rt (int) Math.sqrt(x); return rt * rt x; } }Cclass Solution { // 判断 x 是否为完全平方数 bool is_square(int x) { int rt sqrt(x); return rt * rt x; } public: int numSquarefulPerms(vectorint nums) { int n nums.size(); vector f(1 n, vectorint(n)); ranges::fill(f[0], 1); int u (1 n) - 1; for (int s 1; s u; s) { for (int i 0; i n; i) { if (s i 1) { // i 是填过的数的下标不能在 s 中 continue; } for (int j 0; j n; j) { if (s j 1 is_square(nums[i] nums[j])) { f[s][i] f[s ^ (1 j)][j]; } } } } int ans 0; // 枚举排列的第一个数的下标 for (int i 0; i n; i) { ans f[u ^ (1 i)][i]; } // 去重 unordered_mapint, int cnt; for (int x : nums) { ans / cnt[x]; // 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) } return ans; } };Go// 判断 x 是否为完全平方数 func isSquare(x int) bool { rt : int(math.Sqrt(float64(x))) return rt*rt x } func numSquarefulPerms(nums []int) (ans int) { n : len(nums) f : make([][]int, 1n) for i : range f { f[i] make([]int, n) } for i : range f[0] { f[0][i] 1 } u : 1n - 1 for s : 1; s u; s { for i : range n { if si1 0 { // i 是填过的数的下标不能在 s 中 continue } for j : range n { if sj1 0 isSquare(nums[i]nums[j]) { f[s][i] f[s^1j][j] } } } } // 枚举排列的第一个数的下标 for i : range n { ans f[u^1i][i] } // 去重 cnt : map[int]int{} for _, x : range nums { cnt[x] ans / cnt[x] // 比如 nums 有 3 个 x这里会 /1 再 /2 再 /3从而实现 /(3!) } return }复杂度分析递推版时间复杂度O(n²·2ⁿ)其中 n 是nums的长度每个状态只被计算一次。空间复杂度O(n·2ⁿ)即f数组的大小。五、仓库源码级印证工程化实现与测试验证codeforces-go 仓库在 leetcode/weekly/124/d/ 目录下提供了本题的完整工程化实现与上文递推版解法一一对应可作为落地参考。1. 预计算完全平方数邻接矩阵实现层面的优化仓库 d.go 与题解里的递推代码在算法上完全一致但做了一处值得借鉴的工程化处理预先计算isSquare[i][j]邻接矩阵把每对下标之和是否为完全平方数的结果一次性算好并缓存isSquare : make([][]bool, n) for i, x : range nums { isSquare[i] make([]bool, n) for j, y : range nums { rt : int(math.Sqrt(float64(x y))) isSquare[i][j] rt*rt xy } }这样 DP 主循环内就只剩下isSquare[i][j]的查表操作避免了在 O(n²·2ⁿ) 次转移中反复调用math.Sqrt。当 n 较大或对常数敏感时这种把循环内昂贵的计算提到循环外的预计算模式非常实用。2. 测试驱动的样例验证测试文件 d_test.go 通过仓库自研的 LeetCode 测试框架testutil.RunLeetCodeFuncWithFile直接读取 d.txt 中的用例批量验证func Test_d(t *testing.T) { if err : testutil.RunLeetCodeFuncWithFile(t, numSquarefulPerms, d.txt, 0); err ! nil { t.Fatal(err) } }testutil/leetcode.go 中RunLeetCodeFuncWithFile的实现按函数入参行数 出参行数为单位把测试文件分组由于numSquarefulPerms有 1 个入参nums和 1 个出参答案因此每 2 行为一组用例——[1,17,8]配2、[2,2,2]配1与题目语义完全对应。在仓库根目录执行go test ./leetcode/weekly/124/d/即可运行上述测试验证实现正确性。3. 位运算与状压的通用模板支撑本题是排列型状压 DP 的典型代表其使用的位运算技巧在仓库 search.go 中有系统的模板沉淀包括枚举全集的所有子集for sub : 0; sub 1n; sub枚举某个集合set的所有子集sub (sub - 1) set循环处理完 0 后-1 set set作为结束条件一次跳过一个子集不会遗漏枚举大小为 k 的子集loopSubsetK模板从1k - 1开始通过lb : sub -sub; x : sub lb; sub (sub^x)bits.TrailingZeros(uint(lb))2 | x迭代等价于取下一个组合的位运算写法遍历集合中每个 1 位for ; mask 0; mask mask - 1 { p : bits.TrailingZeros(mask) }。其中枚举子集的子集的跳转正确性说明可见于 search.go思路源自从集合论到位运算的位运算技巧总结。这些模板与本题的u 1n - 1、sj1判断、s^1j删除等操作同属一套位运算体系可以互为印证、配套使用。六、专题训练与延伸本题属于排列型状压 DP的核心训练题。在此基础上可以进一步研读动态规划题单中两个直接相关的进阶专题§9.2 排列型状压 DP ② 相邻相关与本题同属约束条件作用于相邻元素的排列计数类问题转移时通常需要同时记录当前使用的元素集合 上一个元素状态设计与dfs(S, i)同构§9.3 旅行商问题TSPTSP 是排列型状压 DP 的另一大类同样以f[S][last]表示已访问集合 当前所在点的最优值转移按加入新点展开与本题填入下一个数的转移如出一辙。掌握了集合用二进制表示、状态携带上一个元素、转移枚举下一个元素、重复元素做除法去重这四步排列型状压 DP 的大多数题目都可以按同一套路拆解。小结本文以力扣 996「漂亮的排列」为例完整走通了排列型状压 DP 的标准流程拆子问题只看剩余集合 上一个数子问题与原问题同构定义状态dfs(S, i)/f[S][i]用二进制整数表示下标集合设计转移枚举S中与nums[i]之和为完全平方数的j累加dfs(S\{j}, j)记忆化 / 递推两种写法状态定义与转移完全一致可 1:1 互换注意memo初始值不能用要记忆化的值去重收尾答案除以各元素出现次数阶乘的乘积可用递增除法实现。结合 codeforces-go 仓库 d.go 的预计算优化与 d_test.go 的用例验证本文给出的思路既可在比赛中快速推导也可在工程中直接落地复用。对于想巩固这类题型的读者建议优先攻克题单中排列型状压 DP相关章节再进阶 TSP 类问题形成完整的排列计数 DP 能力闭环。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐旅行最大得分 DP 全解从记忆化搜索到递推——codeforces-go 力扣双周赛 142 C 题解析旅行最大得分 DP 全解从记忆化搜索到递推——codeforces go 力扣双周赛 142 C 题解析 本篇技术指南以 codeforces go 仓库中力科学计算codeforces-go 题解精讲网格路径 XOR 值计数 DP——从记忆化搜索到递推的完整推导codeforces go 题解精讲网格路径 XOR 值计数 DP——从记忆化搜索到递推的完整推导 导读 本文以灵茶山艾府在 LeetCode 双周赛 146科学计算codeforces-go 仓库精读力扣双周赛 130 T3「字符频率相等的子串最小划分」——从记忆化搜索到递推的划分型 DP 全解codeforces go 仓库精读力扣双周赛 130 T3「字符频率相等的子串最小划分」——从记忆化搜索到递推的划分型 DP 全解 本篇以 codeforc科学计算上一篇10分钟完成黑苹果配置OpCore-Simplify自动化工具终极指南下一篇如何永久保存微信聊天记录WeChatMsg让数据真正属于你创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考