https://leetcode.com/problems/largest-divisible-subset/description
368. Largest Divisible Subset
給你一個陣列nums,找出由他的元素組成的最大子集合,所有元素滿足
nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0,如果有多個解返回任意一個。
思路:
1.首先把陣列排序,這樣在判斷是否滿足的時候只需要後面的除前面。
2.明顯動態規劃,令 dp[i] 為把 i 位置當結尾的最大子集合,每個子集合初始化為
{nums[i]}。
3.遍歷所有 i 前面的最大子集合,如果滿足 nums[i] % nums[j] == 0 表示 nums[i]
可以加入到 dp[j] 的最大子集合變成一個更大的子集合,令 dp[i] 為這些子集合中
大小最大的。
4.在算的時候用 dp[i] 去更新 res。
Java Code: