本文共 2354 字，大约阅读时间需要 7 分钟。

给你一个由 无重复 正整数组成的集合 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]

动态规划问题：

当前问题：i个元素的最长整除子集

最后一步: i个元素的最长整除子集 = j个元素的最长整除子集 +1，满足nums[i]%nums[j] =0,这里的nums是进行过升序排列之后的

子问题：j个元素的最长整除子集

状态转移方程：f[i] = f[j]+1 and nums[i]%nums[j] = 0 f[i]表示i个元素的最长整除子集 g[i]=j 表示i的最大整除子集是从哪个元素转移来的

初始化和边界条件: f[0] = 1 f[1] = 1 g[i] = i

计算顺序：从0到i开始计算

python代码：

class Solution:    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:        lens = len(nums)        nums.sort()        f,g = [0]*lens,[0]*lens        for i in range(lens):            length ,prev = 1,i            for j in range(i):                if nums[i]%nums[j]==0:                    if f[j]+1>length:                        length = f[j]+1                        prev = j;            f[i] = length                       #记录第i个元素的最长整除子集的长度            g[i] = prev                         #记录每个最长整除子是由哪个元素转移而来        # 找到每个元素对应的最长整除子集长度的最大值        maxlen=idx = -1        for i in range(lens):            if f[i] >maxlen:                 maxlen = f[i]                 idx = i        # 回溯        ans = []        while len(ans)<maxlen:            ans.append(nums[idx])            idx = g[idx]        return  ans

C++

class Solution {
   public:    vector<int> largestDivisibleSubset(vector<int>& nums)    {
          int len = nums.size();       sort(nums.begin(),nums.end());       //动态规划找出最大子集的个数，最大子集中的最大整数       vector<int>dp(len,1);       int maxSize= 1;       int maxVal= dp[0];       for(int i =1;i<len;i++)       {
              for(int j = 0;j<i;j++)           {
                  if(nums[i]%nums[j]==0)               {
                      dp[i] = max(dp[i],dp[j]+1);               }           }           if(dp[i]>maxSize)           {
                  maxSize = dp[i];               maxVal = nums[i];           }       }       vector<int>res;       if(maxSize ==1)       {
              res.push_back(nums[0]);           return res;       }       for(int i = len-1;i>=0&&maxSize>0;i--)       {
              if(dp[i]==maxSize&&maxVal%nums[i]==0)           {
                  res.push_back(nums[i]);               maxVal = nums[i];               maxSize--;           }       }       return res;    }};