题目描述
思路解析动画文字版
记住「排序 → dp[i] 看前面能整除它的、取最长 +1 并记前驱 → 从最长处回溯」,下面逐步套它。
先排序:[5, 9, 18, 54, 108]。排序后只需考虑「大数能否被前面的小数整除」,把问题变成从左到右的链式 DP。
轮到 5(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
定下 dp[0]=1。目前全局最长链的结尾是 5(长度 1)。
轮到 9(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
9 不能被 5 整除(灰),跳过这个候选。
定下 dp[1]=1。目前全局最长链的结尾是 5(长度 1)。
轮到 18(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
18 不能被 5 整除(灰),跳过这个候选。
18 能被 9 整除,且接到 9 的链(长 1)后更长。更新 dp[2]=2,记 18 的前驱是 9。
定下 dp[2]=2。目前全局最长链的结尾是 18(长度 2)。
轮到 54(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
54 不能被 5 整除(灰),跳过这个候选。
54 能被 9 整除,且接到 9 的链(长 1)后更长。更新 dp[3]=2,记 54 的前驱是 9。
54 能被 18 整除,且接到 18 的链(长 2)后更长。更新 dp[3]=3,记 54 的前驱是 18。
定下 dp[3]=3。目前全局最长链的结尾是 54(长度 3)。
轮到 108(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
108 不能被 5 整除(灰),跳过这个候选。
108 能被 9 整除,且接到 9 的链(长 1)后更长。更新 dp[4]=2,记 108 的前驱是 9。
108 能被 18 整除,且接到 18 的链(长 2)后更长。更新 dp[4]=3,记 108 的前驱是 18。
108 能被 54 整除,且接到 54 的链(长 3)后更长。更新 dp[4]=4,记 108 的前驱是 54。
定下 dp[4]=4。目前全局最长链的结尾是 108(长度 4)。
回溯第 1 步:收下 108,再跳到它的前驱 54。绿色是已收集进最大整除子集的数。
回溯第 2 步:收下 54,再跳到它的前驱 18。绿色是已收集进最大整除子集的数。
回溯第 3 步:收下 18,再跳到它的前驱 9。绿色是已收集进最大整除子集的数。
回溯第 4 步:收下 9,它没有前驱,链到头了。绿色是已收集进最大整除子集的数。
回溯结束,最大整除子集 = [9, 18, 54, 108]。链上相邻两数整除(9→18→54→108),靠整除的传递性,任意两数也都整除。
边界:单数返回它;互不整除返回任一个;成链返回全部。
两个延伸:是 LIS 把比较换成整除的变体;整除无全序无法二分到 O(n log n)。
参考代码
from typing import Listclass Solution: def largestDivisibleSubset(self, nums: List[int]) -> List[int]: nums.sort() n = len(nums) dp = [1] * n parent = [-1] * n best = 0 for i in range(n): for j in range(i): if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 parent[i] = j if dp[i] > dp[best]: best = i ans = [] while best != -1: ans.append(nums[best]) best = parent[best] return ans复杂度
- 时间：O(n²)，n 是数组长度。排序 O(n log n);DP 是双重循环 O(n²),取模判整除是 O(1);回溯 O(n)。整体由 O(n²) 主导
- 空间：O(n)，dp 与 parent 数组各 O(n),答案子集 O(n)
易错点
面试追问把动画讲成自己的话
追问这道题和最长递增子序列(LIS)有什么异同?
追问能不能像 LIS 那样用二分把复杂度降到 O(n log n)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
等差数列划分
LeetCode 413 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题