Today's daily question is still a dynamic planning question .

Title Description

Title address ： The largest divisible subset

Dynamic programming

If violence law is considered, how should this problem be done , The easiest way to think of is to enumerate each element as the beginning , Then traverse the other elements . But this method is not reliable , Take an example ：
$[9,18,54,90,108,180,360,540,720]$ Such an array , from 9 If you start, you'll get $[9,18,54,108,540]$, But there are actually longer results $[9,18,90,180,360,720]$, The title requires us to return the longest result , This method is obviously not working .
Let's start thinking about how to use dynamic programming to solve this problem . This problem is a sequence DP problem , Each state depends on the relationship with the previous state , in other words , The current element nums[i] Can you connect it to nums[j] Back , Depending on nums[i] % nums[j] Whether the result is 0. Understand this , So let's define the array dp[],dp[i] Indicates the position of the current element in the sequence . Let's give you an example ：

Defined dp after , How to get dp[i] Well . First, we have to arrange the array from small to large , Because to make nums[i] % nums[j] be equal to 0,nums[i] It must be better than nums[j] Great talent . And then in turn i The previous numbers are % operation , If the result is 0, that dp[i] Is equal to dp[j]+1, That is, in position j After the element of . But because there is more than one element ahead , So we need to update dp[i], Choose the biggest dp[i].
obtain dp Array result , That is, after the results in the table above , Let's go through the table backwards and take out the longest string .

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        dp = [1] * n
        maxSize = 1
        maxVal = dp[0]
        for i in range(1,n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    dp[i] = max(dp[i], dp[j]+1) 
            if dp[i] > maxSize:
                maxSize = dp[i]
                maxVal = nums[i]
        
        res = []
        if maxSize==1:return [nums[0]]
        k = n-1
        while k >= 0:
            if dp[k] == maxSize and maxVal % nums[k] == 0:
                res.append(nums[k])
                maxVal = nums[k]
                maxSize = maxSize-1
            k = k-1
        return res

maxSize The function of is to record the length of the longest sequence , When the result array is finally obtained, each element is added maxSize Just subtract one .maxVal What is recorded is the maximum value of the maximum sequence , Because when you finally get the result, there may be dp Multiple positions of the array are the same number , It needs to be used at this time maxVal Conduct % operation , The result is 0 Is the element of this result sequence .
Last , Because it's traversing backwards , So the final returned results are in reverse order .