368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok) Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

题目大意:给出一个数组，求出一个子数组，子数组中所有的两个数组成的数对可以相互整除。

运用动态规划的方法，dp[i] = dp[j] + 1(如果num[i] % num[j] == 0)

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<int> dp(nums.size(), 0);
        vector<int> son(nums.size(), 0);

        int largest = 0;
        int last = 0;

        for(int i = 0; i < nums.size(); i++){
            for(int j = i; j >= 0; j--){
                if(nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]){
                    dp[i] = dp[j] + 1;
                    son[i] = j;
                }
                if(dp[i] > largest){
                    largest = dp[i];
                    last = i;
                }
            }
        }
        vector<int> res;
        for(int i = 0; i < largest; i++){
            res.insert(res.begin(), nums[last]);
            last = son[last];
        }
        return res;
    }
};

倒过来求这样不用在结果前面插入，从后面开始计算

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<int> dp(nums.size(), 0);
        vector<int> parent(nums.size(), 0);


        int largest = 0;
        int start = 0;
        for(int i = nums.size() - 1; i >= 0; --i){
            //此处j=i对应着上面将dp初始化为0；从后往前迭加，[1,2,4,5,8],效果为[8]->[4, 8]->[2, 4, 8]->[1,2,4,8]
            for(int j = i; j < nums.size(); j++){
                if(nums[j] % nums[i] == 0 && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }

                if(dp[i] > largest){
                    largest = dp[i];
                    start = i;
                }
            }

        }

        vector<int> res;

        for(int i = 0; i < largest; i++){
            res.push_back(nums[start]);
            start = parent[start];
        }
        return res;
    }
};