【leetcode刷题】T169-最大整除子集

• 2019 年 10 月 7 日
• 笔记

木又连续日更第6天（6/100）

动态规划类型第14篇解题报告

leetcode第368题：最大整除子集

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

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

示例 1:  输入: [1,2,3]  输出: [1,2] (当然, [1,3] 也正确)    示例 2:  输入: [1,2,4,8]  输出: [1,2,4,8]  

【思路】

我们首先对nums进行排序，才能使用动态规划。

使用dp[i]存储到第i个元素为止最长整除子集的长度，那么dp[i] = max(1, dp[j]+1)，其中，nums[i] % nums[j] == 0。

取dp数组最大值即可得到最长的整除子集长度。

那么怎么回溯找到整除子集呢？

我们使用parent[i]存储整除子集中i元素的上一位元素。

这样，将所有上一位元素添加至结果中即可。

【代码】

python版本

class Solution(object):      def largestDivisibleSubset(self, nums):          """          :type nums: List[int]          :rtype: List[int]          """          if len(nums) < 1:              return []          nums.sort()          dp = [1] * len(nums)          parent = [i for i in range(len(nums))]          for i, n in enumerate(nums):              for j in range(i-1, -1, -1):                  # dp[i] = max(dp[i], dp[j] + 1)                  if nums[i] % nums[j] == 0:                      if dp[j] + 1 > dp[i]:                          dp[i] = dp[j] + 1                          parent[i] = j            max0 = max(dp)          p = dp.index(max0)          res = []          while True:              res.append(nums[p])              if p == parent[p]:                  break              p = parent[p]          return res  

C++版本

class Solution {  public:      vector<int> largestDivisibleSubset(vector<int>& nums) {          vector<int> res;          if(nums.size() < 1)              return res;          sort(nums.begin(), nums.end());          // 构建dp数组、parent数组          vector<int> dp(nums.size(), 1);          vector<int> parent(nums.size(), 0);          for(int i=1; i<nums.size(); i++){              parent[i] = i;              for(int j=i-1; j>=0; j--){                  if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1){                      dp[i] = dp[j] + 1;                      parent[i] = j;                  }              }          }          // 最大值下标          int p = 0;          for(int i=0; i<dp.size(); i++){              if(dp[p] < dp[i])                  p = i;          }          // 最长序列          while(true){              res.push_back(nums[p]);              if(p == parent[p])                  break;              p = parent[p];          }          return res;      }  };