地址: https://leetcode-cn.com/problems/largest-divisible-subset/
给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
- answer[i] % answer[j] == 0 ，或
- answer[j] % answer[i] == 0 如果存在多个有效解子集，返回其中任何一个均可。
示例1:
输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。
示例2:
输入：nums = [1,2,4,8]
输出：[1,2,4,8]
只求出了合法解，所以没写出来
基本分析 根据题意：对于符合要求的「整除子集」中的任意两个值，必然满足「较大数」是「较小数」的倍数。
数据范围是 10^3，我们不可能采取获取所有子集，再检查子集是否合法的爆搜解法。
通常「递归」做不了，我们就往「递推」方向去考虑。
由于存在「整除子集」中任意两个值必然存在倍数/约数关系的性质，我们自然会想到对 nums 进行排序，然后从集合 nums 中从大到小进行取数，每次取数只考虑当前决策的数是否与「整除子集」中的最后一个数成倍数关系即可。
这时候你可能会想枚举每个数作为「整除子集」的起点，然后从前往后遍历一遍，每次都将符合「与当前子集最后一个元素成倍数」关系的数加入答案。 举个🌰，假设有原数组 [1,2,4,8]，“或许”我们期望的决策过程是：
遍历到数字 1，此时「整除子集」为空，加到「整除子集」中； 遍历到数字 2，与「整除子集」的最后一个元素（1）成倍数关系，加到「整除子集」中； 遍历到数字 4，与「整除子集」的最后一个元素（2）成倍数关系，自然也与 2 之前的元素成倍数关系，加到「整除子集」中； 遍历到数字 8，与「整除子集」的最后一个元素（4）成倍数关系，自然也与 4 之前的元素成倍数关系，加到「整除子集」中。
但这样的做法只能够确保得到「合法解」，无法确保得到的是「最长整除子集」。
考虑反例：[9,18,54,90,108,180,360,540,720]，如果按照我们上述逻辑，我们得到的是 [9,18,54,108,540] 答案（长度为 5），但事实上存在更长的「整除子集」： [9,18,90,180,360,720]（长度为 6）。 其本质是因为同一个数的不同倍数之间不存在必然的「倍数/约数关系」，而只存在「具有公约数」的性质，这会导致我们「模拟解法」错过最优解。
比如上述 🌰，54 & 90 和 18 存在倍数关系，但两者本身不存在倍数关系。
因此当我们决策到某一个数 nums[i] 时（nums 已排好序），我们无法直接将 nums[i] 直接接在符合「约数关系」的、最靠近位置 i 的数后面，而是要检查位置 i 前面的所有符合「约数关系」的位置，找一个已经形成「整除子集」长度最大的数。 换句话说，当我们对 nums 排好序并从前往后处理时，在处理到 nums[i] 时，我们希望知道位置 i 之前的下标已经形成的「整除子集」长度是多少，然后从中选一个最长的「整除子集」，将 nums[i] 接在后面（前提是符合「倍数关系」）。
动态规划 基于上述分析，我们不难发现这其实是一个序列 DP 问题：某个状态的转移依赖于与前一个状态的关系。即 nums[i] 能否接在 nums[j] 后面，取决于是否满足 nums[i] % nums[j] == 0 条件。
可看做是「最长上升子序列」问题的变形题。 定义 f[i]为考虑前 i 个数字，且以第 i 个数为结尾的最长「整除子集」长度。 我们不失一般性的考虑任意位置 i，存在两种情况：
- 如果在 i 之前找不到符合条件 nums[i] % nums[j] == 0 的位置 j，那么 nums[i] 不能接在位置 i 之前的任何数的后面，只能自己独立作为「整除子集」的第一个数，此时状态转移方程为 f[i] = 1；
- 如果在 i 之前能够找到符合条件的位置 j，则取所有符合条件的 f[j] 的最大值，代表如果希望找到以 nums[i] 为结尾的最长「整除子集」，需要将 nums[i] 接到符合条件的最长的 nums[j] 后面，此时状态转移方程为 f[i] = f[j] + 1。
同时由于我们需要输出具体方案，需要额外使用 g[] 数组来记录每个状态是由哪个状态转移而来。
定义 g[i]为记录 f[i] 是由哪个下标的状态转移而来，如果 f[i] = f[j] + 1, 则有 g[i] = j;
对于求方案数的题目，多开一个数组来记录状态从何转移而来是最常见的手段。
当我们求得所有的状态值之后，可以对 f[] 数组进行遍历，取得具体的最长「整除子集」长度和对应下标，然后使用 g[] 数组进行回溯，取得答案。
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
nums.sort()
n = len(nums)
f, g = [0] * n, [0] * n
for i in range(n):
# 至少包含自身一个数，因此起始长度为 1，由自身转移而来
length, prev = 1, i
for j in range(i):
if nums[i] % nums[j] == 0:
# 如果能接在更长的序列后面，则更新「最大长度」&「从何转移而来」
if f[j] + 1 > length:
length = f[j] + 1
prev = j
# 记录「最终长度」&「从何转移而来」
f[i] = length
g[i] = prev
# 遍历所有的 f[i]，取得「最大长度」和「对应下标」
max_len = idx = -1
for i in range(n):
if f[i] > max_len:
idx = i
max_len = f[i]
# 使用 g[] 数组回溯出具体方案
ans = []
while len(ans) < max_len:
ans.append(nums[idx])
idx = g[idx]
ans.reverse()
return ans