美食网站建设策划方案,甘肃建设项目审批权限网站,安徽六安旅游必去十大景点,做i爱小说网站Leetcode 2902. Count of Sub-Multisets With Bounded Sum 1. 解题思路2. 代码实现3. 算法优化 题目链接#xff1a;2902. Count of Sub-Multisets With Bounded Sum
1. 解题思路
这一题有点惭愧#xff0c;因为没有搞定#xff0c;遇上了超时问题……
我的思路其实还是…Leetcode 2902. Count of Sub-Multisets With Bounded Sum 1. 解题思路2. 代码实现3. 算法优化 题目链接2902. Count of Sub-Multisets With Bounded Sum
1. 解题思路
这一题有点惭愧因为没有搞定遇上了超时问题……
我的思路其实还是挺直接的就是直接使用动态规划首先将元素按照unique number进行分组然后分别考察其取用各个数目的情况下的可能情况。
由此基本我们就转换成一个元素取用的动态规划问题剩下的我们就只需要进行剪枝优化即可。
2. 代码实现
给出python代码实现如下
class Solution:def countSubMultisets(self, nums: List[int], l: int, r: int) - int:MOD 10**97cnt Counter(nums)nums sorted(cnt.items(), reverseTrue)n len(nums)accums [0 for _ in range(n1)]for i in range(n-1, -1, -1):accums[i] accums[i1] nums[i][0] * nums[i][1]lru_cache(None)def dp(idx, prev):if idx n:return 1 if l prev r else 0if prev r:return 0if prev accums[idx] l:return 0num, m nums[idx]return sum(dp(idx1, prev i*num) for i in range(m1)) % MODreturn dp(0, 0)不过很不幸的是上述算法一直遇到超时问题最后也没有优化掉这个问题……
3. 算法优化
看了一下大佬们的解答整体依然还是动态规划的思路而且也是需要先将数据按照unique number进行分组。
不过大佬们的解法是直接按照所有的值进行动态规划考察得到某个具体的值的情况下可能的选择方法。
给出大佬们的python代码实现如下
class Solution:def countSubMultisets(self, nums: List[int], l: int, r: int) - int:MOD 10**97cnt Counter(nums)dup cnt[0] 1nums [(k, v) for k, v in cnt.items() if k ! 0]dp [0 for _ in range(r1)]dp[0] 1for num, k in nums:dp_acc [0] * (num r 1)for i in range(r 1):dp_acc[numi] dp_acc[i] dp[i]new_dp [0 for _ in range(r1)]for i in range(r, -1, -1):new_dp[i] (dp_acc[i num] - dp_acc[max(0, i - k * num)]) % MODdp new_dpreturn (sum(dp[l:]) * dup) % MOD提交代码评测得到耗时4445ms占用内存20.4MB。
