Simple Explanation for Optimized Knapsack
PLEASE UPVOTE!\n\n\n# Intuition\n\nKnapsack DP - Count all the multisets with sum k (dp[k]) for all k <= r, then the answer is just sum(dp[l:r+1]). The challeng
PLEASE UPVOTE!\n![crying.jpg](https://assets.leetcode.com/users/images/2fee9109-6f9f-4af0-93d3-8991367f8f3c_1697305532.5117137.jpeg)\n\n# Intuition\n\nKnapsack DP - Count all the multisets with sum `k` (`dp[k]`) for all `k <= r`, then the answer is just `sum(dp[l:r+1])`. The challenge is in optimizing the knapsack so that it can be solved without TLE.\n\n# Approach\nThe code for the "Unoptimized" Knapsack DP is:\n```\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        dp = [1] + [0] * r\n        counts = collections.Counter(nums)\n        for a, c in collections.Counter(nums).items():\n            for k in range(r, -1, -1):\n                dp[k] = sum(dp[k - a*m] for m in range(c+1) if k >= a*m)\n        return sum(dp[l:r+1]) % (10 ** 9 + 7)\n```\n\nWe note that we can optimize out the lowest level loop by precomputing the "strided" sums.\n```\n            ...\n            strided_sums = dp[:]\n            for i in range(a, r + 1):\n                strided_sums[i] += stride_sums[i - a]\n            ...\n```\nThen we can replace the sums with the precomputed values:\n\ni.e replace\n```python3\nsum(dp[k - a*m] for m in range(c+1) if k >= a*m)\n```\n\nwith\n```python3\nif k >= a * c + a:\n    stride_sums[k] - stride_sums[k - a * c - a]\nelse:\n    stride_sums[k]\n```\n\nNote that we also have to be careful here to handle `0` correctly, we just remove all zeros from the counts and multiply the final answer by `counts[0] + 1`.\n\n# Complexity\n- Time complexity:\n$$O(n \\sqrt n)$$ as the number of unique elements is a most $$O(\\sqrt n)$$ - as the sum of k unique elements is $$O(\\sum_k k ) = O(k (k + 1) /2) = O(k ^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        dp = [1] + [0] * r\n        counts = collections.Counter(nums)\n        zeros = counts.pop(0, 0) + 1\n        for a, c in counts.items():\n            stride_sums = dp[:]\n            for i in range(a, r + 1):\n                stride_sums[i] += stride_sums[i - a]\n            for k in range(r, 0, -1):\n                dp[k] = stride_sums[k] - stride_sums[k - a * c - a] if k >= a * c + a else stride_sums[k]\n\n        return zeros * sum(dp[l:r+1]) % (10 ** 9 + 7)\n```
['Dynamic Programming', 'Python3']