[C++/Python] Knapsack DP
Intuition\nKnapsack DP problem, where we can have multiple same item.\n\n\n# Explanation\nIn this Knapsack DP problem,\ndp[i] is the ways to sum up i.\ndp[0] = 
# **Intuition**\nKnapsack DP problem, where we can have multiple same item.\n<br>\n\n# **Explanation**\nIn this Knapsack DP problem,\n`dp[i]` is the ways to sum up `i`.\n`dp[0] = 1` for empty set,\nand we want to find `sum(dp[l] + ... + dp[r])`.\n\nIterate all items,\nassume we have `c` item of size `a`,\niterate `i` from `r` to `1`,\nupdate `dp[i] += dp[i - a] + dp[i - a * 2] + ...+ dp[i - a * c]`.\n\nImprove the process of calculation,\nwith idea of sliding window by keep the sum of\n`dp[i - a] + ... + dp[i - a * c]`\n<br>\n\n# **Complexity**\nTime `O(rm)`\nSpace `O(r)`\nwhere `m` is the number of different `A[i]`,\n`(1 + m) * m / 2 <= sum`,\nso `O(m) = O(sqrt(sum))`\n<br>\n\n**C++**\n```cpp\n    int countSubMultisets(vector<int>& A, int l, int r) {\n        vector<int> dp(20010);\n        dp[0] = 1;\n        int mod = 1e9 + 7;\n        unordered_map<int, int> count;\n        for (int a : A)\n            count[a]++;\n        for (auto it = count.begin(); it != count.end(); ++it) {\n            int a = it->first, c = it->second;\n            for (int i = r; i > max(0, r - a); --i) {\n                long v = 0;\n                for (int k = 0; k < c && i - a * k >= 0; ++k) {\n                    v += dp[i - a * k];\n                }\n                for (int j = i; j > 0; j -= a) {\n                    if (j - a * c >= 0)\n                        v = (v + dp[j - a * c]) % mod;\n                    v = (v - dp[j] + mod) % mod;\n                    dp[j] = (dp[j] + v) % mod;\n                }\n            }\n        }\n        long res = 0;\n        for (int i = l; i <= r; ++i)\n            res = (res + dp[i]) % mod;\n        return res * (count[0] + 1) % mod;\n    }\n```\n\n**Python**\n```py\n    def countSubMultisets(self, A: List[int], l: int, r: int) -> int:\n        dp = [1] + [0] * 50000\n        mod = 10 ** 9 + 7\n        count = Counter(A)\n        for a,c in count.items():\n            for i in range(r, max(r - a, 0), -1):\n                v = sum(dp[i - a * k] for k in range(c))\n                for j in range(i, 0, -a):\n                    v -= dp[j] - dp[j - a * c]\n                    dp[j] = (dp[j] + v) % mod\n        return (count[0] + 1) * sum(dp[l:r + 1]) % mod\n```\n
[]