题目大意：
最大整除子集
给你一个由 无重复 正整数组成的集合 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]
提示：
1 <= nums.length <= 10001 <= nums[i] <= 2 * 109nums中的所有整数 互不相同
解题思路分析：
好久没刷题，还真有些不适应，打开Leetcode后题目居然读了好久才明白。从今开始慢慢恢复元气，咱们继续刷题继续舞。
回到正题，看完题目后我们至少能明确一点，既是我们需要在一个数组中找到一个满足条件的子集。像这种类型的题目，多数只能强撸，但强撸不等同于暴力求解，通常听到的动态规划DP在我看来就属于强撸的范畴，动态规划的精妙之处就在于它使用了一个数组来储存中间过程的计算结果，从而避免了大量重复运算，这是他与暴力解的本质区别。
对于我来讲，所有的动态规划问题我都喜欢转化为dfs深度优先搜索去解决，我在之前的很多文章中都阐述过这个观点，dfs中用到的记忆数组几乎等同于动态规划中的DP数组。本文我们也会使用dfs递归方式来解题。
首先要明确一点，何为整除子集？简单来讲就是集合中所有数字之间都是倍数关系。如果将数字由小到大排列后，比如: [2, 4, 8, 16, 64] ，我们轻易可以看出，任何一个数字都是其左侧数字的倍数。这一点很重要，它将是我们接下来编写递归函数的基础。
无论是动态规划，还是dfs，实际上都是将复杂问题简单化，然后再由一个个简单问题推演出复杂结果的过程。本题我们可以先提出一个通用问题，即在一个排序好的数组中，下标为i的元素的右侧（index>=i）包含多少它的倍数？提出这个问题的原因是我们需要从数组的第一位（下标0）向右搜索，如果当前数字是前数字的倍数，那么我们通过上述问题的解就可以算出数组第一位身后所有的倍数个数，接下来我们再使用相同的方式以数组第二位，第三位为起点向后搜索，并找出一个最长路径（数组子集）即可。
举个例子，比如说数组[2, 3, 4, 6, 8]中，我们先以2作为起点向后搜索，走到数字3的位置时，由于3不是2的倍数，所以这条路不通，我们重新从2出发走到数字4的位置，这时4是2的倍数，此时如果我们能够通过某种神秘力量得知4的身后有N（肉眼可知N等于2）个4的倍数的话（包括4本身），那么2的倍数个数一定是1+N（等于3，即[2, 4, 8]这个子集）。同理接下来以3为起点开始向后搜索，结果是[3, 6]，该集合小于前一结果。再然后分别以4， 6， 8为起点计算的结果都不是最优解，因此本题答案是[2, 4, 8]这个子集。
那么问题来了，我们如何才能得知下标为i的元素的右侧（index>=i）包含多少它的倍数呢？通过上面的例子我们应该知道，提出这一问题的前提应该是当前数字是搜索路径上前一数字的倍数才行，否则此路是不通的。也就是说dfs路径上每一个节点都是起点的倍数时，该路径才有效。因此当前数字不是前一数字倍数时，当前路径的终点应该到前一数字为止。反之，如果当前数字是前一数字倍数时，当前节点也可加入到路径之中，同时需要继续尝试向后延伸。向后延伸时，dfs会派生出多条路径，当前节点右侧的每一个数字都可以作为路径的下一个节点，比如数组[2, 3, 4, 6, 8]，4的前一节点是2，而他的后一节点可以连接到6，也可以是8。所有路径最长的那一个即是当前的解。之后的延伸处理交给递归子问题去解决即可，逻辑和当前问题一致。递归的终止条件是当前数字不是前一节点的倍数，或者当前数字是数组尾元素的时候。
以上就是递归的基本逻辑，接下来再考虑一下记忆数组就完事大吉。题目要求列出最大子集合，那么记忆数组中我们就存集合好了。最后我们看代码来具体分析。
实现代码：
class Solution {
List<Integer>[] memo; // 记忆数组
List<Integer> resList = new ArrayList(); // 返回结果
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums); // 先排序数组
memo = new List[nums.length]; // 初始化记忆数组
for(int i=0;i<nums.length;i++){ // 分别以每个数字作为起点
List<Integer> res = dfs(nums, i, 1); // dfs走起
if(res.size()>resList.size()) { // 更新全局最大值
resList = res;
}
}
return resList;
}
// dfs递归函数
// nums: 数组
// index: 当前节点下标
// preNum: dfs路径中前一节点
// 返回值：当前节点的倍数数组（包含当前节点）
private List<Integer> dfs(int[] nums, int index, int preNum) {
int num = nums[index]; // 当前数字
if(num % preNum != 0){ // 如果当前数字不是前一数字的倍数，返回空数组
return new ArrayList();
}
// 记忆数组存在当前结果的话直接返回，避免重复计算
if(memo[index] != null) return memo[index];
List<Integer> maxList = new ArrayList(); // 当前递归返回结果
for(int j = index + 1; j<nums.length;j++){ // 循环接下来的每一条分叉路经
List<Integer> res = dfs(nums, j, num); // 子问题结果（下一节点的倍数数组）
if(res.size()> maxList.size()){ // 如果该结果个数大于其他路径
maxList = new ArrayList(res); // 更新当前最大值
}
}
maxList.add(num); // 将当前节点加入到集合中
memo[index] = maxList; // 将当前结果存入记忆数组
return maxList; // 返回当前结果给上层递归
}
} 本题解法执行时间为44ms。
Runtime: 44 ms, faster than 8.66% of Java online submissions for Largest Divisible Subset.Memory Usage: 39.6 MB, less than 40.75% of Java online submissions for Largest Divisible Subset.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-368-largest-divisible-subset-解题思路分析/