题目描述：

LeetCode 368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (S_i, S_j) of elements in this subset satisfies: S_i % S_j = 0 or S_j % S_i = 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]

题目大意：

给定一个不重复正整数集合，寻找最大子集，使得子集中的任意一对元素 (Si, Sj) 均满足Si % Sj = 0或者Sj % Si = 0。

如果存在多种答案，返回其中之一即可。

测试用例如题目描述。

解题思路：

动态规划（Dynamic Programming）

状态转移方程：

dp[x] = max(dp[x], dp[y] + 1)  其中： 0 <= y < x 且 nums[x] % nums[y] == 0

返回结果利用辅助数组pre记录

Python代码：

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nums = sorted(nums)
        size = len(nums)
        dp = [1] * size
        pre = [None] * size
        for x in range(size):
            for y in range(x):
                if nums[x] % nums[y] == 0 and dp[y] + 1 > dp[x]:
                    dp[x] = dp[y] + 1
                    pre[x] = y
        idx = dp.index(max(dp))
        ans = []
        while idx is not None:
            ans += nums[idx],
            idx = pre[idx]
        return ans

一种简短的解法，来自LeetCode Dicuss：https://leetcode.com/discuss/110905/4-lines-in-python

Python代码：

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        S = {-1: set()}
        for x in sorted(nums):
            S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
        return list(max(S.values(), key=len))

 

本文链接：http://bookshadow.com/weblog/2016/06/27/leetcode-largest-divisible-subset/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码