# Python DP with detailed subproblem explanations

• 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]


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