Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2024-02-09 12:25:19
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:

Links booklink

Contact Us: admin [ a t ] ucptt.com