368. 最大整除子集

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/largest-divisible-subset/
Star
给你一个由 无重复 正整数组成的集合 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]
提示：
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2 * 109
  • nums 中的所有整数 互不相同
通过次数40,454提交次数88,179
#法1 动态规划
思路
题目是在问最大整除子集，而不是在问最大整除子集的长度！
如果是问最大整除子集的长度，那么按照
🀄
300. 最长递增子序列 的解法求得最大整除子集长度。当然不同的是300题子序列有顺序，所以需要判断nums[i] > nums[j]，而本题是没有顺序的，是子集，即为子集合。所以可以事先对nums进行排序，或者不排序直接采用 nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0 来判断是否可以整除。
当然以上均为求最大子集长度的解法。那要怎么就求解最大子集本身呢？
按照动态规划的思路，之前是存放最大整除子集长度，那么可不可以存放子集本身呢。当然可以，只是更新dp的时候，不是采用max(dp[i], dp[j]+1) ,而只能采用朴素的if判断长度然后添加nums[j]到dp[i]中。
题解
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        # 先排好序
        nums.sort()

        dp = [[i] for i in nums] 
        for i in range(1, len(dp)):
            for j in range(i-1, -1, -1):
                if nums[i] % nums[j] == 0:
                    if len(dp[i]) < len(dp[j]) + 1:
												# 将数字加进去  
												# 这一步之前都是 dp[i] = dp[j] + 1，
                        # 但是此时dp[i] 为存放的具体集合，所以需要添加元素
                        dp[i] = dp[j] +  [nums[i]] 

        return max(dp, key=len)