368. Largest Divisible Subset

题目

https://leetcode.com/problems/largest-divisible-subset/description/

想法

排序

能整除集合中的最大的数，那么也会属于这个集合

直觉DP..

遇到一个新数，从此数前一个开始判断，是否可以并入
维护更新max

好像需要回溯来做，需要记录序列

backtracking

回溯写了个，TLE

class Solution {
private:
    vector<int> res;
    vector<int> curr;
    void f(vector<int>& nums, int idx) {
        for (int i = idx; i < nums.size(); i++) {
            if (curr.empty() || nums[i] % curr[curr.size() - 1] == 0) { // #1
                curr.push_back(nums[i]);
                f(nums, i + 1);
                curr.pop_back();
            }       
        }
        if (curr.size() > res.size()) {
            res = curr;
        }
    }
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if (nums.empty())
            return res;
        sort(nums.begin(), nums.end());
        f(nums, 0);
        return res;
    }
};

感觉是剪枝做得不够充分..

1 2 4

1 2 之后，就不应该试1 4了，肯定比1 2..少
这个怎么剪呢？

将上述代码中#1部分改动：

if (curr.empty() || (find(res.begin(), res.end(), nums[i]) == res.end() && nums[i] % curr[curr.size() - 1] == 0))

AC，但是时间是1540ms，显然勉强AC

DP

if (nums[i] % nums[j] == 0)
dp[i] = max(dp[j] + 1, dp[i])

参考了https://leetcode.com/problems/largest-divisible-subset/discuss/83999/Easy-understood-Java-DP-solution-in-28ms-with-O(n2)-time
虽然他的有bug

最后运行16ms，还好

这里关键的一点是选取最后的结果上，注意筛选方式：

if (dp[i] == dp[idx] - res.size() && prev % nums[i] == 0)

答案

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> res;
        if (nums.empty())
            return res;
        sort(nums.begin(), nums.end());
        vector<int> dp(nums.size(), 1);
        for (int i = 1; i < nums.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int idx = distance(dp.begin(), max_element(dp.begin(), dp.end()));
        cout << idx;
        int prev = nums[idx];
        for (int i = idx; i >= 0; i--) {
            if (dp[i] == dp[idx] - res.size() && prev % nums[i] == 0) {
                res.push_back(nums[i]);
                prev = nums[i];
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};