摘要

有时候我们会遇到这样的问题：给定一堆数，如何从中挑出一个子集，让这个子集里的每一对数都能互相整除？题目要求我们找出最大的这样一个子集。

这个问题看起来有点像是在“组团”，条件是必须能整除。其实背后是一个动态规划问题，用来锻炼我们对“子问题递推”的理解。

描述

题目给了一个数组 nums，里面是一些互不相同的正整数。我们要找出一个最大的子集 answer，使得里面的任意两个数 a 和 b 满足：

• a % b == 0，或者
• b % a == 0。

换句话说，要么一个能被另一个整除，要么反过来也能被整除。

示例 1：

输入: [1,2,3]
输出: [1,2]
解释: 其实 [1,3] 也对，因为 3 % 1 == 0。

示例 2：

输入: [1,2,4,8]
输出: [1,2,4,8]

题解答案

直观的思路是：

1. 如果一个数可以整除另一个数，那它们更可能属于同一个子集。
2. 子集要尽量大，所以我们需要在多个候选方案中找到“最长的那条链”。

动态规划的做法：

• 先把数组排序，因为小数更容易整除大数。

• 用一个数组 dp[i] 表示以 nums[i] 结尾的最大整除子集的长度。

• 遍历每个 nums[i]，再和前面的数 nums[j] 去比较：

  • 如果 nums[i] % nums[j] == 0，说明能放在一起，那就更新 dp[i] = max(dp[i], dp[j] + 1)。

• 同时用一个 parent 数组来记录前驱，方便最后回溯出完整的子集。

题解代码分析

下面是 Swift 的实现：

import Foundationclass Solution {func largestDivisibleSubset(_ nums: [Int]) -> [Int] {if nums.isEmpty { return [] }let nums = nums.sorted()let n = nums.countvar dp = Array(repeating: 1, count: n) // 每个数至少能独立成一个集合var parent = Array(repeating: -1, count: n) // 用来回溯路径var maxLen = 1var maxIndex = 0for i in 1..<n {for j in 0..<i {if nums[i] % nums[j] == 0 {if dp[j] + 1 > dp[i] {dp[i] = dp[j] + 1parent[i] = j}}}if dp[i] > maxLen {maxLen = dp[i]maxIndex = i}}// 回溯答案var result = [Int]()var k = maxIndexwhile k != -1 {result.append(nums[k])k = parent[k]}return result.reversed()}
}// MARK: - Demo 演示
let solution = Solution()
print(solution.largestDivisibleSubset([1, 2, 3]))    // [1, 2] 或 [1, 3]
print(solution.largestDivisibleSubset([1, 2, 4, 8])) // [1, 2, 4, 8]
print(solution.largestDivisibleSubset([3, 5, 10, 20, 21])) // [5, 10, 20]

代码拆解

1. 排序

   • 把数组排好序，保证前面的数比后面的小，便于判断整除关系。

2. 动态规划数组 dp

   • dp[i] 表示以 nums[i] 结尾的最大整除子集的长度。

3. 前驱数组 parent

   • parent[i] 记录了 nums[i] 前面可以接上的数字位置，用来回溯结果。

4. 两层循环

   • 外层 i 表示当前要计算的数。
   • 内层 j 遍历比它小的数，看能不能整除。

5. 回溯结果

   • 从最大长度的下标开始，不断回溯 parent，拼成最终的子集。

示例测试及结果

运行 Demo，结果如下：

输入: [1, 2, 3]
输出: [1, 2]   // 或 [1, 3]输入: [1, 2, 4, 8]
输出: [1, 2, 4, 8]输入: [3, 5, 10, 20, 21]
输出: [5, 10, 20]

这个结果是合理的，比如 [5, 10, 20] 就是一条完整的整除链：

• 10 % 5 == 0
• 20 % 10 == 0

时间复杂度

• 外层循环 i 最多跑 n 次，内层循环 j 也最多 n 次。
• 所以时间复杂度是 O(n²)。
• 在 n <= 1000 的范围内，这个复杂度是可接受的。

空间复杂度

• 使用了 dp 和 parent 两个数组，各占 O(n)。
• 回溯的结果也是 O(n)。
• 所以整体空间复杂度是 O(n)。

总结

这道题的关键在于 先排序，再动态规划：

• 排序后更容易保证“整除链”的关系。
• 动态规划帮我们一步步延长最长的整除子集。

如果用现实场景来打个比方：

• 你可以把每个数想象成一个“圈子”，只有能整除的才能成为同一个圈子。
• 我们要找的，就是那个能容纳最多成员的“最大圈子”。

这类题目训练了我们对 递推关系 的思考能力，也再次证明了排序在动态规划里的重要作用。