题目描述
这是 LeetCode 上的 368. 最大整除子集 。
Tag : 「序列 DP」
给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
- answer[i] % answer[j] == 0 ，或
- answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。
示例 1：
输入：nums = [1,2,3] 输出：[1,2] 解释：[1,3] 也会被视为正确答案。 复制代码
示例 2：
输入：nums = [1,2,4,8] 输出：[1,2,4,8] 复制代码
提示：
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 2 * 10910^9109
- nums 中的所有整数 互不相同
基本分析
根据题意：对于符合要求的「整除子集」中的任意两个值，必然满足「较大数」是「较小数」的倍数。
数据范围是 10310^3103，我们不可能采取获取所有子集，再检查子集是否合法的爆搜解法。
通常「递归」做不了，我们就往「递推」方向去考虑。
由于存在「整除子集」中任意两个值必然存在倍数/约数关系的性质，我们自然会想到对 nums 进行排序，然后从集合 nums 中从大到小进行取数，每次取数只考虑当前决策的数是否与「整除子集」中的最后一个数成倍数关系即可。
这时候你可能会想枚举每个数作为「整除子集」的起点，然后从前往后遍历一遍，每次都将符合「与当前子集最后一个元素成倍数」关系的数加入答案。
举个🌰，假设有原数组 [1,2,4,8]，“或许”我们期望的决策过程是：
- 遍历到数字
1，此时「整除子集」为空，加到「整除子集」中； - 遍历到数字
2，与「整除子集」的最后一个元素（1）成倍数关系，加到「整除子集」中； - 遍历到数字
4，与「整除子集」的最后一个元素（2）成倍数关系，自然也与2之前的元素成倍数关系，加到「整除子集」中； - 遍历到数字
8，与「整除子集」的最后一个元素（4）成倍数关系，自然也与4之前的元素成倍数关系，加到「整除子集」中。
但这样的做法只能够确保得到「合法解」，无法确保得到的是「最长整除子集」。
当时担心本题数据太弱，上述错误的解法也能够通过，所以还特意实现了一下，还好被卡住了（🤣
同时也得到这个反例：[9,18,54,90,108,180,360,540,720]，如果按照我们上述逻辑，我们得到的是 [9,18,54,108,540] 答案（长度为 5），但事实上存在更长的「整除子集」： [9,18,90,180,360,720]（长度为 6）。
其本质是因为同一个数的不同倍数之间不存在必然的「倍数/约数关系」，而只存在「具有公约数」的性质，这会导致我们「模拟解法」错过最优解。
比如上述 🌰，54 & 90 和 18 存在倍数关系，但两者本身不存在倍数关系。
因此当我们决策到某一个数 nums[i] 时（nums 已排好序），我们无法直接将 nums[i] 直接接在符合「约数关系」的、最靠近位置 i 的数后面，而是要检查位置 i 前面的所有符合「约数关系」的位置，找一个已经形成「整除子集」长度最大的数。
换句话说，当我们对 nums 排好序并从前往后处理时，在处理到 nums[i] 时，我们希望知道位置 i 之前的下标已经形成的「整除子集」长度是多少，然后从中选一个最长的「整除子集」，将 nums[i] 接在后面（前提是符合「倍数关系」）。
动态规划
基于上述分析，我们不难发现这其实是一个序列 DP 问题：某个状态的转移依赖于与前一个状态的关系。即 nums[i] 能否接在 nums[j] 后面，取决于是否满足 nums[i] % nums[j] == 0 条件。
可看做是「最长上升子序列」问题的变形题。
定义 f[i]f[i]f[i] 为考虑前 i 个数字，且以第 i 个数为结尾的最长「整除子集」长度。
我们不失一般性的考虑任意位置 i，存在两种情况：
- 如果在
i之前找不到符合条件nums[i] % nums[j] == 0的位置j，那么nums[i]不能接在位置i之前的任何数的后面，只能自己独立作为「整除子集」的第一个数，此时状态转移方程为 f[i]=1f[i] = 1f[i]=1； - 如果在
i之前能够找到符合条件的位置j，则取所有符合条件的f[j]的最大值，代表如果希望找到以nums[i]为结尾的最长「整除子集」，需要将nums[i]接到符合条件的最长的nums[j]后面，此时状态转移方程为 f[i]=f[j]+1f[i] = f[j] + 1f[i]=f[j]+1。
同时由于我们需要输出具体方案，需要额外使用 g[] 数组来记录每个状态是由哪个状态转移而来。
定义 g[i]g[i]g[i] 为记录 f[i]f[i]f[i] 是由哪个下标的状态转移而来，如果 f[i]=f[j]+1f[i] = f[j] + 1f[i]=f[j]+1, 则有 g[i]=jg[i] = jg[i]=j。
对于求方案数的题目，多开一个数组来记录状态从何转移而来是最常见的手段。
当我们求得所有的状态值之后，可以对 f[] 数组进行遍历，取得具体的最长「整除子集」长度和对应下标，然后使用 g[] 数组进行回溯，取得答案。
代码：
class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); int n = nums.length; int[] f = new int[n]; int[] g = new int[n]; for (int i = 0; i < n; i++) { // 至少包含自身一个数，因此起始长度为 1，由自身转移而来 int len = 1, prev = i; for (int j = 0; j < i; j++) { if (nums[i] % nums[j] == 0) { // 如果能接在更长的序列后面，则更新「最大长度」&「从何转移而来」 if (f[j] + 1 > len) { len = f[j] + 1; prev = j; } } } // 记录「最终长度」&「从何转移而来」 f[i] = len; g[i] = prev; } // 遍历所有的 f[i]，取得「最大长度」和「对应下标」 int max = -1, idx = -1; for (int i = 0; i < n; i++) { if (f[i] > max) { idx = i; max = f[i]; } } // 使用 g[] 数组回溯出具体方案 List<Integer> ans = new ArrayList<>(); while (ans.size() != max) { ans.add(nums[idx]); idx = g[idx]; } return ans; } } 复制代码
- 时间复杂度：O(n2)O(n^2)O(n2)
- 空间复杂度：O(n)O(n)O(n)
证明
之所以上述解法能够成立，问题能够转化为「最长上升子序列（LIS）」问题进行求解，本质是利用了「全序关系」中的「可传递性」。
在 LIS 问题中，我们是利用了「关系运算符 ⩾\geqslant⩾ 」的传递性，因此当我们某个数 a 能够接在 b 后面，只需要确保 a⩾ba \geqslant ba⩾b 成立，即可确保 a 大于等于 b 之前的所有值。
那么同理，如果我们想要上述解法成立，我们还需要证明如下内容：
- 「倍数/约数关系」具有传递性
由于我们将 nums[i] 往某个数字后面接时（假设为 nums[j]），只检查了其与 nums[j] 的关系，并没有去检查 nums[i] 与 nums[j] 之前的数值是否具有「倍数/约数关系」。
换句话说，我们只确保了最终答案 [a1, a2, a3, ..., an] 相邻两数值之间具有「倍数/约数关系」，并不明确任意两值之间具有「倍数/约数关系」。
因此需要证得由 a∣ba | ba∣b 和 b∣cb | cb∣c，可推导出 a∣ca | ca∣c 的传递性：
由 a∣ba | ba∣b 可得 b=x∗ab = x * ab=x∗a由 b∣cb | cb∣c 可得 c=y∗bc = y * bc=y∗b
最终有 c=y∗b=y∗x∗ac = y * b = y * x * ac=y∗b=y∗x∗a，由于 xxx 和 yyy 都是整数，因此可得 a∣ca | ca∣c。
得证「倍数/约数关系」具有传递性。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.368 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
