基于动态规划算法的基本解决方案


  • 0
    W
    # 基于动态规划算法
    class Solution(object):
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            nums = sorted(nums) # 排序
            opt = [1 for i in range(0, len(nums))]
            pre = [None]*len(nums)
            if len(nums) > 0:
                for i in range(0, len(nums)):
                    for j in range(0, i):
                        if int(nums[i]) % int(nums[j]) == 0 and opt[i] < opt[j] + 1:  # OPT(k)= max{opt(k),opt(j)+1}
                            opt[i] = opt[j] + 1
                            pre[i] = j  # 回溯数组,记录获得当前最长子数组的前一个最长子序列
                index = opt.index(max(opt))
                ans = []
                while index is not None:
                    ans.append(nums[index])
                    index = pre[index]
                return ans
            else:
                return []
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.