LC 2902. 和带限制的子多重集合的数目

看了题解才知道这个是多重背包问题。之前也不知道这种问题有什么好的解法，题解总结挺好的，两类方法：滚动数组和前缀和。两种方法其实都不是特别难理解，公式也还好，我把代码直接贴在下面。

其实这题我最没有想通的就是时间复杂度，如果还是按照DP的话，那么就是 `O(NM)` 了，其中N是nums长度，M是和上限。但是其实两者之间是存在某些关系的：因为对于最坏情况，nums里面每个值是不同的话，O(N^2) = O(M). 所以这里其实更像是 O(M^(3/2)) 这个时间复杂度上。如果按照题目提示中说的， `M < 2*10^4` 的话，那么这个时间复杂度是可以接受的。

class Solution:
    def countSubMultisets(self, nums: List[int], L: int, R: int) -> int:
        from collections import Counter
        cnt = Counter(nums)

        f = [cnt[0] + 1] + [0] * R
        del cnt[0]

        upper = 0
        MOD = 10 ** 9 + 7
        for x, c in cnt.items():
            new_f = f.copy()
            upper = min(upper + x * c, R)
            for j in range(x, upper + 1):
                new_f[j] += new_f[j - x]
                if j >= (c + 1) * x:
                    new_f[j] -= f[j - (c + 1) * x]
                new_f[j] %= MOD
            f = new_f
        return sum(f[L:]) % MOD


class Solution:
    def countSubMultisets(self, nums: List[int], L: int, R: int) -> int:
        from collections import Counter
        cnt = Counter(nums)

        f = [cnt[0] + 1] + [0] * R
        del cnt[0]

        upper = 0
        MOD = 10 ** 9 + 7
        for x, c in cnt.items():
            upper = min(upper + x * c, R)
            for j in range(x, upper + 1):
                f[j] = (f[j] + f[j - x]) % MOD
            for j in reversed(range((c + 1) * x, upper + 1)):
                f[j] = (f[j] - f[j - (c + 1) * x]) % MOD

        return sum(f[L:]) % MOD