分析

// 由于 c % b == 0, b % a == 0 => c % a == 0
// 约分具有传递性

// 根据条件，返回vec中的较小的数，必然是较大的数的公因数
// 更具体的说，每个大的数，是全部比它小的数的倍数
// DFS，每一层可选可不选，更深的层次只能选后面的
// 每次选择，判断是否和能够和cache中最后一个数整除，有的话也放进去
// 时间复杂度。。。
// 第一层: n
// 第二层: n-1, n-2, ..., 1, 0 = (n-1)**2
// 第三层: n-2, n-3, ..., 0 = (n-2)**2
// 暴力搜索，时间复杂度：1 + 2**2 + ... + n**2 = n**3 = 1e9, 必定超时

// 怎么优化？
// 是否存在重复计算的部分呢？
// 我们观察可以发现:
// 排序之后，如果 b % a == 0的话，那么后面以b为约数的数总是确定的
// 如果说这个数已经被搜索过了，那么就可以临时保存这个结果
// 记忆化搜索：时间复杂度O(N ** 2)

// 如果用动态规划
// 因为我们发现，以某个数为约数的数是确定的，说明了无后效性
// f(i): 最大后缀的集合
// 属性: 长度，下一个元素的索引
// 状态转移如何运算？
// f(i) == 满足 nums[k+1] % nums[i] == 0的k:
// f(i+1) ... f(n)中最大长度的索引maxk, 那么f(i) == {f(maxk).len + 1, maxk}

算法1

(暴力枚举) $O(n^2)$

这个记忆化的形式，可以优化的，优化方法看下面的DP解法

C++ 代码

class Solution {
private:
    unordered_map<int, vector<int>> map;
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> tv;
        dfs(-1, nums, tv);
        return map[-1];
    }

    void dfs(int s, vector<int>& nums, vector<int> tv) {
        if(map.find(s) != map.end()) 
            return;
        int n = nums.size();
        if(s >= 0) map[s].push_back(nums[s]);
        int msize = 0, mi = -1;
        for(int i = s+1; i < n; i++) {
            if(s < 0 || nums[i] % nums[s] == 0) {
                dfs(i, nums, tv);
                if(map[i].size() > msize) msize = map[i].size(), mi = i;
            }
        }
        for(auto t : map[mi]) map[s].push_back(t);
    }
};

class Solution {
private:
    unordered_map<int, pair<int, int>> map;
    int msize, mi;
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        msize = 0, mi = -1;
        dfs(-1, nums);

        vector<int> ans(msize);
        for(int i = mi, idx = 0; idx < msize; i = map[i].second, idx++)
            ans[idx] = nums[i];
        return ans;
    }

    void dfs(int s, vector<int>& nums) {
        if(map.find(s) != map.end()) 
            return;
        int n = nums.size();
        int msize = 0, mi = -1;
        for(int i = s+1; i < n; i++) {
            if(s < 0 || nums[i] % nums[s] == 0) {
                dfs(i, nums);
                if(map[i].first > msize) msize = map[i].first, mi = i;
            }
        }
        if(s >= 0) msize++;
        map[s].first = msize;
        map[s].second = mi;
        if(msize > this->msize) {
            this->msize = msize;
            this->mi = s;
        }
    }
};

算法2

(DP) $O(n^2)$

C++ 代码

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<pair<int, int>> f(n, {0, -1});
        int msize = 0, mi;
        for(int i = n-1; i >= 0; i--) {
            for(int j = i+1; j < n; j++) {
                if(nums[j] % nums[i] == 0) {
                    if(f[j].first > f[i].first) {
                        f[i].first = f[j].first;
                        f[i].second = j;
                    }                    
                }
            }
            f[i].first++;
            if(f[i].first > msize) {
                msize = f[i].first;
                mi = i;
            }
        }
        vector<int> ans(msize);
        for(int i = mi, idx = 0; idx < msize; i = f[i].second, idx++)
            ans[idx] = nums[i];
        return ans;
    }
};