leetcode 368. Largest Divisible Subset 最大分割子集+LISS最长递增子序列+动态规划DP

落日映苍穹つ 2022-06-07 02:45 147阅读 0赞

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\]

仔细想一下，这道题可以转化为和LISS最长递增子序列一样的问题去使用DP动态规划求解，这道题很值得反思。

**注意要先排序**

建议和[leetcode 300. Longest Increasing Subsequence 最长递增子序列LISS + 十分经典的动态规划DP做法][leetcode 300. Longest Increasing Subsequence _LISS _ _DP] 、[leetcode 354. Russian Doll Envelopes 俄罗斯套娃 + 动态规划DP + 类似LISS最长递增子序列的做法][leetcode 354. Russian Doll Envelopes _ _ _DP _ _LISS]和[leetcode 646. Maximum Length of Pair Chain 最长连续元素][leetcode 646. Maximum Length of Pair Chain] 一起学习

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /*
     * 和LISS最长递增子序列做法思路完全一样
     * 
     * 1.先将数字排序；
     * 2.dp[i]表示nums[i]可以整除的最多数；
     * 3.有递推公式 dp[i]=max(dp[i],dp[j]+1) if dp[i]%dp[j]==0, j<i;
     * */
    class Solution 
    {
        public List<Integer> largestDivisibleSubset(int[] nums) 
        {
            List<Integer> res=new ArrayList<>();
            if(nums==null || nums.length<=0)
                return res;
            if(nums.length==1)
            {
                res.add(nums[0]);
                return res;
            }
            int[] dp=new int[nums.length];
            Arrays.fill(dp, 1);
            int [] pre=new int[nums.length];
            for(int i=0;i<nums.length;i++)
                pre[i]=i;
    
            int maxLen=0,maxIndex=0;
            Arrays.sort(nums);
            for(int i=0;i<nums.length;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(nums[i]%nums[j]==0 && dp[j]+1>dp[i])
                    {
                        dp[i]=dp[j]+1;
                        pre[i]=j;
                    }   
                }
                if(dp[i]>maxLen)
                {
                    maxLen=dp[i];
                    maxIndex=i;
                }
            }
    
            int i=maxIndex;
            while(pre[i]!=i)
            {
                res.add(nums[i]);
                i=pre[i];
            }
            res.add(nums[i]);
            return res;
        }
    }

下面是C++的做法

仔细想一下，这个其实就是一个LISS最长递增子序列的问题，解决方法基本一样，不过要记得对数组做一次排序

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) 
        {
            vector<int> res;
            if (nums.size() <= 0)
                return res;
    
            sort(nums.begin(), nums.end());
    
            vector<int> len(nums.size(), 1);
            vector<int> pre(nums.size(), 0);
            for (int i = 0; i < pre.size(); i++)
                pre[i] = i;
    
            int maxNum = 0, index = 0;
            for (int i = 0; i < pre.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (nums[i] % nums[j] == 0 && len[j] + 1 > len[i])
                    {
                        len[i] = len[j] + 1;
                        pre[i] = j;
                    }
                }
    
                if (len[i] > maxNum)
                {
                    maxNum = len[i];
                    index = i;
                }
            }
    
            int i = index;
            while (pre[i] != i)
            {
                res.push_back(nums[i]);
                i = pre[i];
            }
            res.push_back(nums[i]);
            return res;
        }
    };

[leetcode 300. Longest Increasing Subsequence _LISS _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78122446
[leetcode 354. Russian Doll Envelopes _ _ _DP _ _LISS]: http://blog.csdn.net/jackzhang_123/article/details/78173297
[leetcode 646. Maximum Length of Pair Chain]: http://blog.csdn.net/jackzhang_123/article/details/78862409