[LeetCode]Dp368 最大整除子集 [思路同Dp300]

传送门：https://leetcode-cn.com/problems/largest-divisible-subset/

题目

给你一个由 无重复 正整数组成的集合 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. 1 <= nums.length <= 1000
2. 1 <= nums[i] <= 2 * 109
3. nums中的所有整数 互不相同

前言

首先需要理解什么叫「整除子集」。根据题目的描述，如果一个所有元素互不相同的集合中的任意元素存在整除关系，就称为整除子集。

根据整除关系具有传递性，即如果 ，并且 ，那么 ，可知：

• 若整数 是整除子集 的最小整数 的约数（即 ），则将 添加到 中会得到更大的整除子集；
• 若整数 是整除子集 的最大整数 的约数（即 ），则将 添加到 中会得到更大的整除子集；

这两点揭示了当前问题状态转移的特点，因此可以使用动态规划的方法求解。事实上，当前问题和使用动态规划解决的经典问题「🚩300. 最长递增子序列」有相似之处。

解题思路：动态规划

我们需要将输入数组 按照升序排序，以便获得一个子集的最小整数或者最大整数。

定义 dp[i] 表示在输入数组 nums 升序排列的前提下，以 nums[i] 结尾所能构成的「整除子集」的最大值
（在这种定义下 必须被选择）
贴条：nums[i] / nums[j]
枚举 j=[0…i−1] 的所有整数 nums[j]，若 nums[j] 能整除 nums[i]，说明 nums[i] 可以在以 nums[j] 为最大整数的整除子集里成为一个更大的整除子集。

解释： 整除 是 。 是被除数， 是除数。

初始化 由于 nums[i] 必须被选择，因此对于任意 i=0…n−1，初始的时候 dp[i]=1， n 是输入数组的长度。

状态转移方程：

Dp表：

Size：

计算后的Dp表：

不难发现，利用动态规划可以找出最大的序列，却无法记录下最大子集，因此我们需要在Dp表中找出最长子集

1. 倒序遍历数组 dp，找到 dp[i]=maxSize ，把对应的 nums[i] 加入结果集，此时 maxVal=nums[i]；
2. 将 maxSize 的值减 1，继续倒序遍历 i 找到 dp[i]=maxSize，且 nums[i] 能整除 maxVal ，将此时的 nums[i] 加入结果集，maxVal 更新为此时的 num[i]；
3. 重复上述操作，直到 _maxSize_ 的值变成 0，此时的结果集即为一个目标子集。

举例子：

1. 根据 dp 的计算结果，maxSize=4，maxVal=16，故大小为 4 的最大整除子集包含的最大整数为 16
2. 然后查大小为 3 的最大整除子集，我们看到 8 和 12 对应的状态值都是 3，最大整除子集一定包含 8，这是因为 8|16
3. 然后查大小为 2 的最大整除子集，我们看到 4 对应的状态值是 2，最大整除子集一定包含 4；
4. 然后查大小为 1 的最大整除子集，我们看到 2 对应的状态值是 1，最大整除子集一定包含 2；

通过这样的方式，我们就找到了满足条件的某个最大整除子集 [16,8,4,2]。

复杂度分析

时间复杂度：，其中 为数组 的长度。

对数组 排序的时间复杂度为 ，计算数组 元素的时间复杂度为 ，倒序遍历得到一个目标子集，时间复杂度为 。

空间复杂度：，，其中 为数组 的长度。

代码

官方代码

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        // 第 1 步：动态规划找出最大子集的个数、最大子集中的最大整数
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int maxSize = 1;
        int maxVal = dp[0];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                // 题目中说「没有重复元素」很重要
                if (nums[i] % nums[j] == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            //节省一次倒序遍历,在计算中标记最大值
            if (dp[i] > maxSize) {
                maxSize = dp[i];
                maxVal = nums[i];
            }
        }
        // 第 2 步：倒推获得最大子集
        List<Integer> res = new ArrayList<Integer>();
        if (maxSize == 1) {
            res.add(nums[0]);
            return res;
        }
        for (int i = len - 1; i >= 0 && maxSize > 0; i--) {
            if (dp[i] == maxSize && maxVal % nums[i] == 0) {
                res.add(nums[i]);
                maxVal = nums[i];
                maxSize--;
            }
        }
        return res;
    }
}