368.最大整除子集

dp, https://leetcode.cn/problems/largest-divisible-subset/description/

给你一个由 无重复 正整数组成的集合 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 * 10^9
nums 中的所有整数 互不相同

python

from typing import List

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        
        # 对数组进行排序，确保可以从小到大检查整除关系
        nums.sort()
        n = len(nums)
        
        # dp[i] 表示以 nums[i] 结尾的最大整除子集的大小
        dp = [1] * n
        # prev[i] 记录 dp[i] 的前驱索引，用于回溯构造结果
        prev = [-1] * n
        
        max_size = 1  # 最大整除子集的大小
        max_index = 0  # 最大整除子集的最后一个元素的索引
        
        # 动态规划计算 dp 和 prev
        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0:  # 满足整除条件
                    if dp[j] + 1 > dp[i]:  # 更新 dp[i]
                        dp[i] = dp[j] + 1
                        prev[i] = j  # 记录前驱
            # 更新最大整除子集的信息
            if dp[i] > max_size:
                max_size = dp[i]
                max_index = i
        
        # 回溯构造最大整除子集
        result = []
        while max_index != -1:
            result.append(nums[max_index])
            max_index = prev[max_index]
        
        # 返回结果（需要逆序）
        return result[::-1]

代码说明

排序：
- 首先对 nums 进行排序，这样可以确保在后续动态规划中只需要检查 nums[i] % nums[j] == 0 而不需要同时检查 nums[j] % nums[i] == 0。
动态规划：
- 使用一个 dp 数组来记录以每个元素结尾的最大整除子集的大小。
- 使用一个 prev 数组来记录每个元素的前驱索引，方便最后回溯构造结果。
状态转移方程：
- 如果 nums[i] % nums[j] == 0，则 dp[i] = max(dp[i], dp[j] + 1)，并更新 prev[i] = j。
回溯构造结果：
- 找到 dp 中的最大值及其对应的索引，然后通过 prev 数组回溯构造最大整除子集。
时间复杂度：
- 排序的时间复杂度为 $O (n l o g n)$ 。
- 动态规划部分需要两层嵌套循环，时间复杂度为 $O (n^{2})$ 。
- 总体时间复杂度为 $O (n^{2})$ ，适合题目给定的数据范围（n ≤ 1000）。

368.最大整除子集 ​

368.最大整除子集