Python DP with detailed subproblem explanations


  • 0
    1

    This is a very typical DP problem, to handle it we should first figure out what the subproblem is.
    Suppose (num_1, num_2, ... , num_{n-1}, num_n) is a divisible subset sorted in ascending order, according to the problem's definition, every pair (num_i, num_j) satisfies num_i % num_j == 0 or num_j % num_i == 0, so it's easy to find out that num_n must be the multiple of all the elements in (num_1, num_2, ... , num_{n-1}). Now here comes a new element num_{n+1} which is greater than num_n, if num_{n+1} is a multiple of num_n, then obviously num_{n+1} is also the multiple of all the elements in (num_1, num_2, ... , num_{n-1}), which makes the new set (num_1, num_2, ... , num_{n-1}, num_n, num_{n+1}) a divisible subset!
    We have now found the subproblem, let's define it in a more formal way:
    s[i]: the largest divisible subset that ends with num[i] as the largest element
    s[i] = max_{j \in [0, i), num[i] % num[j] == 0}(s[j] + 1)
    base case: s[0] = [num[0]]
    below is the code, we first sort nums in ascending order, than we do the DP:


    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        (s_1, s_2, ..., s_n) is a divisible subset sorted in increasing order, so s_n is a multiple of s1, s1, ...,s_{n-1}, if s_{n+1} is larger than s_n and is a multiple of s_n, than (s_1, s_2, s_3, ..., s_n, s_{n+1}) is also a divisible subset.
        let s[i] denote the largest divisible subset that ends with nums[i] as the largets element.
                    s[i] = max_{j \in [0, i), nums[i] % nums[j] = 0}{s[j]} + 1
                    base case: s[0] = [nums[0]]
        """
        l = len(nums)
        if not l:
            return []
        nums.sort()
        s = [(1, [nums[0]])]# base case, [size, elements]
        for i in range(1, l):
            ms = max([s[j] for j in range(i) if nums[i] % nums[j] == 0] or [(0, [])], key = lambda x:x[0]) 
            s.append((ms[0] + 1, ms[1] + [nums[i]]))
        return max(s, key = lambda x:x[0])[1]
    


Log in to reply
 

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