【4.23】LeetCode每日一题· 最大整除子集

2021年04月23日 17时13分

标签： LeetCode 动态规划

## 题目描述
给你一个由 无重复 正整数组成的集合`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 中的所有整数 互不相同
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/largest-divisible-subset "题目链接")

## 解题思路
看到题目后的我第一想法是，如何判断一个数`n`是否在某一个整除子集中呢？发现如果`n`能整除小于它的最大整数，且能被大于它的最小整数整除时，`n`就能加入这个整除集中。因此就遍历每一个整数，贪心地找到其能够加入的最大整除集中就将其加入，找不到就新建一个集合。最后输出最大的集合作为答案。

但上述思路前半部分是对的，但后半部分不对。因为向整除集中插入某一个数字，会对后面的整数是否可以插入该整除集产生影响，因此所得出的结果可能不是最优的。例如对于`[1, 3, 6, 9, 27]`，正确的答案应该是`[1, 3, 9, 27]`，而对于我的算法来说答案是`[1, 3, 6]`，因为贪心导致了6这一含有因子2的数被引入了。

下面说正解：动态规划。

在我的思考部分的前半部分实际上已经思考出了如下的性质：
**整除**这具有**传递性**，也就是说如果**a整除b**（记为$$a|b$$）,且**b整除c**，那么有**a整除c**，即

$$a|b,\, b|c \\Rightarrow a|c \qquad (a \\geq b \\geq c)$$

由条件可设$$b=k_1a$$，$$c = k_2b$$，因此有$$c = k_1k_2a$$即**a整除c**。

因此，就可以考虑如何通过一个较小的整除集扩展到另一个较大的整除集。首先将`nums`从小到大排序。然后记
```
dp[i] := 必包含nums[i]的最大整除子集的大小
```
则有：
```
初始条件：dp[i] = 1
状态转移方程：
	dp[i] = max{dp[k] + 1 if nums[i] % nums[k] == 0} for k in range(0, i)
```
这样就可以得到最大的整除子集的大小，然后通过建立的动态规划表格回溯就可以得到有效子集，方法如下：
```
回溯答案：
从右往左找到第一个dp[i] = max{dp[k]}，然后找下一个满足dp[j] == dp[i]-1 && nums[i] % nums[j] == 0的位置。
将所有得到的{nums[i]}逆序排列就是一个有效解子集
```

PS：
在看到题目时，由于一般做到的动态规划题答案都是一个数字，而不是一个集合，没有考虑到回溯答案，因此没有朝动态规划这一方面想。实际上如果能定义出状态的话，得出本题的状态转移方程和回溯的方法还是比较简单的。

## 代码
```cpp
class Solution {
public:
    // 现将nums从小到大排序
    // dp[i] := 必包含nums[i]的最大整除子集的大小
    // 初始条件：dp[i] = 1
    // dp[i] = max{dp[k] + 1 if nums[i] % nums[k] == 0} for k in range(0, i)
    // 回溯答案：
    // 从右往左找到第一个dp[i] = max{dp[k]}，然后找下一个满足dp[j] == dp[i]-1 && nums[i] % nums[j] == 0的位置。
    // 将所有得到的{nums[i]}逆序排列就是一个有效解子集
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        const int N = nums.size();
        sort(nums.begin(), nums.end());
        int dp[N];
        for(int i = 0; i < N; i++){
            dp[i] = 1;
            for(int k = 0; k < i; k++){
                if(nums[i] % nums[k] == 0){
                    dp[i] = max(dp[i], dp[k]+1);
                }
            }
        }
        // 找到最大长度lenToFind，和对应整除子集中的最大数numn
        int lenToFind = 0, num;
        for(int i = 0; i < N; i++){
            if(lenToFind <= dp[i]){
                lenToFind = dp[i];
                num = nums[i];
            }
        }
        // 从右往左回溯答案
        vector<int> res;
        for(int i = N-1; i >= 0; --i){
            if(dp[i] != lenToFind) continue;
            if(num % nums[i] != 0) continue;
            num = nums[i];
            lenToFind--;
            res.insert(res.begin(), num);
        }
        return res;
    }
};
```

### 用时和内存
> 执行用时：40 ms，在所有 C++提交中击败了98.25%的用户
> 内存消耗：8.4 MB，在所有 C++提交中击败了86.13%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.23】LeetCode每日一题· 最大整除子集

所有评论

暂无评论

新增评论