如何仅使用长度（和结束位置）来记忆最长可整子集？

Question

目标是找到最大的可整子集。可除子集是 s.t. 的子集。对于每对元素 i、j，要么 i 可被 j 整除，要么 j 可被 i 整除。解决这个问题的一般方法是对数字进行排序，并认识到如果 a 可被 b 整除且 b 可被 c 整除，则 a 也必须可被 c 整除。这是未记忆的递归：

def largestDivisibleSubset0(self, nums: List[int]) -> List[int]:
    def backtrack(candidate, end):
        if len(candidate) > len(self.best):
            self.best = candidate[:]

        if end == n - 1:
            return

        for new_end in range(end+1, n):
            if not candidate or candidate[-1] % nums[new_end] == 0:
                backtrack(candidate+[nums[new_end]], new_end)

    nums.sort(reverse=True)
    n = len(nums)
    self.best = []
    backtrack([], -1)
    return self.best

接下来，我尝试记忆。请原谅

self.best

和备忘录都被跟踪的糟糕风格。我知道这是多余的，而且我实际上并没有缓存本地最好的，而是缓存全局的（附带问题：什么是记住这一点的最佳方法？）

def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
    def backtrack(candidate, end):
        if (len(candidate), end) in memo:
            return memo[(len(candidate), end)]

        if len(candidate) > len(self.best):
            self.best = candidate[:]

        if end == n - 1:
            return

        for new_end in range(end+1, n):
            if not candidate or candidate[-1] % nums[new_end] == 0:
                backtrack(candidate+[nums[new_end]], new_end)

        memo[(len(candidate), end)] = self.best

    nums.sort(reverse=True)
    n = len(nums)
    self.best = []
    memo = {}
    backtrack([], -1)
    return self.best

这是我不明白的地方。简单地考虑当前候选的长度而不是最后一个元素的长度如何准确地表示状态？如果以 5 结尾的子序列的长度为 x，等于以 4 结尾的子序列，那么后一个序列是否有可能从搜索空间中被修剪掉，即使它可能会导致更长的可整除子集？

Answer 1

end

告诉您候选子序列结尾。

如果以 5 结尾的子序列的长度为 x，等于以 4 结尾的子序列怎么办

然后他们的

end

不同，因此他们的备忘录键不同，因此他们不会互相修剪。