Python, knapsack dp solution with explanation
knapsack dp\nThe problem ask that how many ways to fill up [l, r]size of knapsacks,\nand if numbers are the same, there are the same items.\ndp[i][j] is number 
### knapsack dp\nThe problem ask that how many ways to fill up ```[l, r]```size of knapsacks,\nand if numbers are the same, there are the same items.\ndp[i][j] is number of ways to fill up size j of knapsack.\nwe have ```y``` of number ```x```,\ndp[i][j] = dp[i-1][j] + dp[i-1][j-x] + dp[i-1][j-2x] + ... + dp[i-1][j-y*x].\n\nand j = j-x (mod x)= j-2x (mod x) = ... = j-y* x(mod x),\nwe can use prefix sum to get dp[i-1][j] + dp[i-1][j-x] + dp[i-1][j-2x] + ... + dp[i-1][j-y*x],\nFirst, calculate prefix sum of same remainder of x,\ndp[j] += dp[j-x],\nand  we only have ```y``` of number ```x```,\nso, dp[j] - dp[j - (y + 1) * x].\n\ntc is O(r * number of distinct item in nums), sc is O(r).\n```python\nMOD = int(1e9+7)\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        cnt = defaultdict(int)\n        dp = [0] * (1 + r)\n        dp[0] = 1\n        for x in nums:\n            if x == 0:\n                dp[0] += 1\n            elif x <= r:\n                cnt[x] += 1\n        for x, y in cnt.items():\n            for j in range(x, 1 + r):\n                dp[j] = (dp[j] + dp[j - x]) % MOD\n            for j in range(r, (1 + y) * x - 1, -1):\n                dp[j] = (dp[j] - dp[j - (y + 1) * x] + MOD) % MOD\n        return reduce(lambda acc, x: (acc + dp[x]) % MOD, range(l, r+1), 0)\n```\n\n### optimization\n1. if sum of nums < l, return 0\n2. maximum size of knapsack is max(r, sum of nums) \n```python\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        sum_ = 0\n        cnt = defaultdict(int)\n        for x in nums:\n            if x <= r:\n                cnt[x] += 1\n            sum_ += x\n        if l > sum_:\n            return 0\n        r = min(r, sum_)\n        dp = [0] * (1 + r)\n        dp[0] = 1 + cnt[0]\n        del cnt[0]\n        for x, y in cnt.items():\n            for j in range(x, 1 + r):\n                dp[j] = (dp[j] + dp[j - x]) % MOD\n            for j in range(r, (1 + y) * x - 1, -1):\n                dp[j] = (dp[j] - dp[j - (y + 1) * x] + MOD) % MOD\n        return reduce(lambda acc, x: (acc + dp[x]) % MOD, range(l, r+1), 0)\n```
['Prefix Sum', 'Python']