LeetCode 3336 题解子序列最大公约数相等的对计数DP 三状态枚举 记忆化递归【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以 LeetCode 3336「最大公约数相等的子序列数量」为核心讲解如何用动态规划统计两个互不相交、且元素 GCD 相等的子序列对的数量。文章继承了原题解的「逐个元素三选一」思路并结合仓库中的 动态规划专题、最大公约数专题 与同类题目源码如 416. 分割等和子集深入剖析状态定义、转移方程与复杂度边界。读完你不仅能 AC 本题还能掌握一类「把元素划分到若干集合」的计数 DP 通用套路。题目描述与输入约束给你一个整数数组nums请你统计所有满足以下条件的非空子序列对(seq1, seq2)的数量子序列seq1和seq2不相交即nums中不存在同时出现在两个序列中的下标seq1元素的GCD等于seq2元素的 GCD。由于答案可能非常大请返回其对10^9 7取余的结果。输入约束决定了算法量级必须控制在n * m^2级别1 nums.length 200 1 nums[i] 200三个示例用于验证对题意的理解nums [1,2,3,4]输出1010 个 GCD 均为 1 的子序列对nums [10,20,30]输出22 个 GCD 均为 10 的子序列对nums [1,1,1,1]输出50。注意题面中「元素 GCD 等于 1 的子序列对有」下列出的 10 项只是示意列举实际计数的是具体的下标划分方案而不是被打印成相同样式的字面量这也是示例 3 能产出 50 的原因——每种子序列划分按下标唯一计数。前置知识与仓库关联本题的前置知识标注为动态规划实际还隐式依赖**最大公约数GCD**的计算。仓库中恰好有两篇与本题直接相关的专题文章可作为扩展阅读最大公约数专题系统梳理了三种 GCD 求法——定义法O(min(a,b))、辗转相除法O(log(max(a,b)))、更相减损术并指出「辗转相除 更相减损」结合可获得更稳的性能。本题代码中的math.gcd底层正是辗转相除法。动态规划专题开篇即点明「动态规划和查表的递归记忆化递归有很多相似的地方」并强调「定义状态是动态规划的核心」「时间复杂度打底就是状态总数」这些观点正是理解本题dp(i, gcd1, gcd2)设计的关键。GCD 概念上子序列的 GCD 是其中所有元素的最大公约数gcd(a, b, c) gcd(gcd(a, b), c)因此可以随着逐个放入元素逐步累积计算这为下面的三选一 DP 提供了前提。核心思路把元素逐个放入两个集合一类计数题的通用框架像这种要求把元素划分为若干个集合本题是两个集合 可丢弃的计数题通常考虑枚举元素逐个放入集合对每个元素枚举它放入哪个集合根据题目也可以不放入任何集合。本题正是这种「逐个元素三选一」的模型。与之相对的「枚举集合再考虑放入哪些元素」的方式由于集合个数通常远小于元素个数一般没有优势不推荐。注意这里说的是集合元素之间的顺序无影响。如果题目要求的是有序排列顺序有影响这种逐个放入的方式就不可行了。本题中对每个nums[i]恰好有三种决策放入seq1放入seq2不放入任何序列。当数组全部处理完后若seq1与seq2的 GCD 相同则这组划分方案对答案贡献 1。为什么可以用 DP无后向性与重叠子问题这个「逐个元素三选一」的过程天然满足 DP 的两大条件无后向性当前元素放入哪个集合只会影响后续状态中的gcd1/gcd2取值不会回头改变前面已确定的划分因此可以从左到右递推重叠子问题不同路径会到达相同的(i, gcd1, gcd2)状态比如[2,3]与[3,2]不同的放入顺序可能产生相同的 GCD 组合若不做记忆化暴力枚举所有三选一分支的时间复杂度是指数级的。仓库 动态规划专题 对此有明确的印证「递归中如果存在重复计算重叠子问题那就是使用记忆化递归或动态规划解题的强有力信号之一」。状态定义与转移方程状态定义定义dp[i][gcd1][gcd2]从下标i开始即尚未决策的元素为nums[i:]当前seq1的最大公约数为gcd1、seq2的最大公约数为gcd2的前提下剩余元素划分完毕后、两序列 GCD 相等的方案总数。最终答案为dp(0, -1, -1)其中-1表示对应序列尚未放入任何元素空序列没有 GCD用哨兵值-1区分边界条件dp[n][x][x] 1其中x的范围是[1, m]m为值域本题m 200。含义是所有元素都已决策完毕i n若两个序列都非空且gcd1 gcd2则这一种完整划分方案计数为 1否则为 0。转移方程对当前元素nums[i]枚举三种决策dp(i, gcd1, gcd2) dp(i 1, gcd(gcd1, nums[i]), gcd2) // 放入 seq1 dp(i 1, gcd1, gcd(gcd2, nums[i])) // 放入 seq2 dp(i 1, gcd1, gcd2) // 不放入任何序列转移中的一个小技巧当序列为空gcd -1时放入第一个元素后 GCD 应直接等于该元素本身即gcd(-1 哨兵, x) x代码中用gcd1 if gcd1 ! -1 else nums[i]处理。这也说明状态中的-1只是一个特殊哨兵并不参与真正的 GCD 计算。复杂度分析令n为数组长度m为数组值域状态个数为n * m^2每个状态的转移是O(1)时间复杂度O(n * m^2)。代入本题约束n 200, m 200约8 * 10^6量级的状态可以接受空间复杂度O(n * m^2)若用记忆化递归实际空间还包含递归调用栈开销。参考代码Python3记忆化递归原题解使用 Python3 的cache记忆化装饰器实现自顶向下 DPclass Solution: def subsequencePairCount(self, nums: List[int]) - int: MOD 10 ** 9 7 cache def dp(i, gcd1, gcd2): if i len(nums): if gcd1 gcd2 and gcd1 ! -1: return 1 return 0 ans dp(i 1, math.gcd(gcd1 if gcd1 ! -1 else nums[i], nums[i]), gcd2) dp(i 1, gcd1, math.gcd(gcd2 if gcd2 ! -1 else nums[i], nums[i])) dp(i 1, gcd1, gcd2) return ans % MOD return dp(0, -1, -1)代码要点拆解cache等价于手动维护memo[(i, gcd1, gcd2)]哈希表key 为函数参数元组value 为返回值这正是仓库 动态规划专题 中「查表的递归记忆化递归」的标准形态三个dp(...)分支分别对应「放入 seq1」「放入 seq2」「都不放入」与思路部分的三种决策一一对应每个状态在返回前对MOD取余防止累加溢出边界判断gcd1 ! -1保证两序列均为非空题目要求非空子序列对。关于记忆化递归 vs 迭代 DP 的选择仓库 动态规划专题 给出的建议同样适用于本题「没空间优化需求直接就记忆化否则用迭代 dp」——本题状态维度较多三维滚动数组优化收益有限记忆化递归是更直观、不易出错的写法。与仓库同类题目的横向印证本题「逐个元素三选一 累计 GCD」的模型在仓库中能找到多个可对照学习的姊妹题416. 分割等和子集同样是「元素放入两组」的划分模型F[i, v]表示前i个数能否组成和为v的子序列本质是背包问题它与本题的差异在于 416 的两个集合必须恰好覆盖所有元素相当于没有「不放入」这个第三选项且目标约束是「和相等」而非「GCD 相等」。494. 目标和将数组分成组和-组两组也是划分计数 DP可对照理解「集合划分 方案计数」的套路。365. 水壶问题 与 914 等 GCD 应用展示了 GCD 在判定类问题中的应用z是否能被gcd(x, y)整除与本题「用 GCD 作为状态维度」形成互补视角。从源码结构可以推断本题的价值在于把「GCD」这一数学算子与「集合划分计数 DP」结合GCD 的幂等、可累积性质gcd(gcd(a,b), c) gcd(a,b,c)使得「放入序列后只更新该序列的 GCD 一个维度」成为可能这是状态能压缩为三维的关键。总结识别模型看到「划分成两个或多个不相交集合 满足某个相等条件 计数」时优先考虑「逐个元素枚举放入哪个集合」的 DP 框架状态设计dp(i, gcd1, gcd2)把「处理到哪」和「两个集合当前 GCD」全部纳入状态用-1哨兵表示空序列转移即三选一放入 seq1 / 放入 seq2 / 都不放三个分支各对应一个子问题边界收口全部元素处理完后仅当两个序列非空且 GCD 相等时计数 1复杂度可控O(n * m^2)的时间与空间在n, m 200的量级下完全可行。扩展阅读最大公约数专题三种 GCD 求法动态规划专题记忆化递归与状态定义416. 分割等和子集集合划分 DP / 背包模型494. 目标和正负两组划分计数365. 水壶问题GCD 判定应用【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考