leetcode 368. Largest Divisible Subset | 368. 最大整除子集（动态规划详解）

Myth丶恋晨 2022-08-29 13:59 143阅读 0赞

## 题目 ##

[https://leetcode.com/problems/largest-divisible-subset/][https_leetcode.com_problems_largest-divisible-subset]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]  
哎，动态规划对我来说仍然是玄学…

只要有动态规划，medium is harder than hard  
只要没有动态规划，hard is easier than medium

## 题解 ##

动态规划问题，没想出来，看了答案。

另外，相似问题：[leetcode 300. Longest Increasing Subsequence | 300. 最长递增子序列（动态规划）][leetcode 300. Longest Increasing Subsequence _ 300.]

本题解参考：[【宫水三叶の相信科学系列】详解为何能转换为序列 DP 问题][DP]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]

class Solution { 
        public List<Integer> largestDivisibleSubset(int[] nums) { 
            Arrays.sort(nums);
            int[] dp = new int[nums.length];
            int[] trace = new int[nums.length];
            for (int i = 0; i < dp.length; i++) { 
                dp[i] = 1;
                for (int j = 0; j < i; j++) { 
                    if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) { 
                        dp[i] = dp[j] + 1;
                        trace[i] = j;
                    }
                }
                if (dp[i] == 1) trace[i] = -1;
            }
    
            int maxLength = 0;
            int maxIndex = 0;
            for (int i = 0; i < dp.length; i++) { 
                if (dp[i] > maxLength) { 
                    maxLength = dp[i];
                    maxIndex = i;
                }
            }
            
            ArrayList<Integer> list = new ArrayList<>();
            int p = maxIndex;
            while (p != -1) { 
                list.add(nums[p]);
                p = trace[p];
            }
            return list;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode.com_problems_largest-divisible-subset]: https://leetcode.com/problems/largest-divisible-subset/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/b2a6d0d1f30e46739f107d328141effa.png
[leetcode 300. Longest Increasing Subsequence _ 300.]: https://blog.csdn.net/sinat_42483341/article/details/118487526
[DP]: https://leetcode-cn.com/problems/largest-divisible-subset/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-0a3jc/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/25eac96ec77c42c4a22d19d4d4d7c984.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20220829/578533c1e4e04c2b80a5856250e69e13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20220829/cee7242f421145e399ba00fa3920a7db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/bf90ba3e91ce411db4f6ec309696d2f4.png