問題背景

給你一個由 無重復 正整數組成的集合 $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;}
}