元宝 LeetCode 2902. 和带限制的子多重集合的数目 Python3实现
以下是 LeetCode 2902 题"和带限制的子多重集合的数目"的 Python3 实现代码。这个解决方案使用动态规划和多重背包优化技术，时间复杂度为 O(n + r·√Σ(nums[i]))，其中 n 是数组长度，r 是上限值。
from typing import List
from collections import Counter
class Solution:
def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
MOD = 1_000_000_007
# 1. 统计频率
counter = Counter(nums)
# 2. 处理数字0
zeros = counter.get(0, 0)
if 0 in counter:
del counter[0]
# 3. 动态规划数组
dp = [0] * (r + 1)
dp[0] = 1
# 4. 多重背包转移
for num, freq in counter.items():
# 如果数字大于r，可以跳过
if num > r:
continue
# 计算前缀和
prefix = dp[:] # 复制当前dp数组
# 计算不考虑次数限制的前缀和
for i in range(num, r + 1):
prefix[i] = (prefix[i] + prefix[i - num]) % MOD
# 更新dp，扣除超过freq次的方案
limit = num * (freq + 1)
for i in range(r, -1, -1):
if i >= limit:
dp[i] = (prefix[i] - prefix[i - limit]) % MOD
else:
dp[i] = prefix[i] % MOD
# 5. 累加区间[l, r]的方案数
result = 0
for i in range(l, r + 1):
result = (result + dp[i]) % MOD
# 6. 乘以0的贡献（每个0可选可不选）
return (result * (zeros + 1)) % MOD
# 测试用例
def test_solution():
solution = Solution()
# 测试用例1
nums1 = [1, 2, 2, 3]
l1, r1 = 3, 5
result1 = solution.countSubMultisets(nums1, l1, r1)
print(f"测试用例1: nums={nums1}, l={l1}, r={r1}")
print(f"结果: {result1}")
print()
# 测试用例2
nums2 = [0, 0, 1, 2, 3]
l2, r2 = 1, 3
result2 = solution.countSubMultisets(nums2, l2, r2)
print(f"测试用例2: nums={nums2}, l={l2}, r={r2}")
print(f"结果: {result2}")
print()
# 测试用例3
nums3 = [1, 1, 1, 1]
l3, r3 = 2, 3
result3 = solution.countSubMultisets(nums3, l3, r3)
print(f"测试用例3: nums={nums3}, l={l3}, r={r3}")
print(f"结果: {result3}")
print()
# 测试用例4
nums4 = [2, 3, 5]
l4, r4 = 5, 5
result4 = solution.countSubMultisets(nums4, l4, r4)
print(f"测试用例4: nums={nums4}, l={l4}, r={r4}")
print(f"结果: {result4}")
print()
# 测试用例5: 空集
nums5 = [1, 2, 3]
l5, r5 = 0, 0
result5 = solution.countSubMultisets(nums5, l5, r5)
print(f"测试用例5: nums={nums5}, l={l5}, r={r5}")
print(f"结果: {result5}")
if __name__ == "__main__":
test_solution()
关键点说明
算法思路：
使用多重背包的动态规划方法
通过前缀和优化将时间复杂度从 O(n×r×cnt) 降低到 O(n×r)
特殊处理数字0，因为它不影响和但影响方案数
核心步骤：
统计每个数字的出现频率
处理数字0，因为0可以选择任意多个，但不会增加和
使用动态规划计算每个可能的和的方案数
对每个数字使用前缀和技巧优化多重背包转移
最后累加[l, r]区间内的方案数，并乘以0的贡献
时间复杂度：
主要部分：O(r × 不同数字的个数)
当r=2×10⁴时，这是可接受的
空间复杂度：
O(r)，使用一维DP数组
额外使用O(n)的空间存储频率统计
边界情况处理：
处理数字0的情况
处理数字大于r的情况（可以直接跳过）
处理空集合的情况（和为0）
这个实现能够高效地计算满足条件的子多重集合的数目，并正确处理各种边界情况。