【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;      }  };