LeetCode_动态规划_中等_368.最大整除子集

今天药忘吃喽~ 2023-10-06 23:39 27阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/largest-divisible-subset

## 2.思路 ##

（1）动态规划  
思路参考[该 LeetCode 用户题解][LeetCode]。

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public static List<Integer> largestDivisibleSubset(int[] nums) {
        
            List<Integer> res = new ArrayList<>();
            Arrays.sort(nums);
            int length = nums.length;
            // f[i] 表示数组 nums 中以第 i 个数结尾的最长整除子集的长度
            int[] f = new int[length];
            // g[i] 记录 f[i] 是由哪个下标的状态转移而来，如果 f[i] = f[j] + 1, 则有 g[i] = j
            int[] g = new int[length];
            for (int i = 0; i < length; i++) {
        
                int len = 1, prev = 1;
                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 < length; i++) {
        
                if (f[i] > max) {
        
                    idx = i;
                    max = f[i];
                }
            }
            //使用数组 g 回溯出具体方案
            while (res.size() != max) {
        
                res.add(nums[idx]);
                idx = g[idx];
            }
            return res;
        }
    }

[LeetCode]: https://leetcode.cn/problems/largest-divisible-subset/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-0a3jc/