【Leetcode 每日一题】368. 最大整除子集

问题背景

给你一个由 无重复 正整数组成的集合 $nums$，请你找出并返回其中最大的整除子集 $answer$，子集中每一元素对 $(answer[i],answer[j])$ 都应当满足：

• $answer[i]\%answer[j]=0$，或
• $answer[j]\%answer[i]=0$
  如果存在多个有效解子集，返回其中任何一个均可。

数据约束

• $1\le nums.length\le 1000$
• $1\le nums[i]\le 2\times 10^9$
• $nums$ 中的所有整数 互不相同

解题过程

生成答案的过程，应当是在已经形成的子集中尝试添加新元素，最终结果是从规模更小的解转移而来，用动态规划解决，类似 最长递增子序列。

具体实现

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] memo = new int[n];
        int[] from = new int[n];
        Arrays.fill(from, -1);
        int res = 0;
        int index = 0;
        for (int i = 0; i < n; i++) {
            int cur = dfs(i, nums, memo, from);
            if (cur > res) {
                res = cur;
                index = i;
            }
        }
        List<Integer> path = new ArrayList<>(res);
        for (int i = index; i >= 0; i = from[i]) {
            path.add(nums[i]);
        }
        return path;
    }

    private int dfs(int i, int[] nums, int[] memo, int[] from) {
        if (memo[i] > 0) {
            return memo[i];
        }
        int res = 0;
        for (int j = 0; j < i; j++) {
            if (nums[i] % nums[j] != 0) {
                continue;
            }
            int cur = dfs(j, nums, memo, from);
            if (cur > res) {
                res = cur;
                from[i] = j;
            }
        }
        return memo[i] = res + 1;
    }
}