C++ - Bottom up DP
Intuition\nI first came up with top down DP but got OOM. Then looked into https://leetcode.com/problems/count-of-sub-multisets-with-bounded-sum/solutions/416806
# Intuition\nI first came up with top down DP but got OOM. Then looked into https://leetcode.com/problems/count-of-sub-multisets-with-bounded-sum/solutions/4168064/optimized-dynamic-programming/ to implement bottom up DP solution. \n\n# Code\n```\nclass Solution {\n    int MOD = 1000000007;\n   \npublic:\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        unordered_map<int,int> m;\n        \n        for (auto n: nums) m[n]++;\n\n        vector<int> dp(r+1,0);\n        dp[0]=1;\n        for (auto [k,v]: m){\n            vector<int> cp(dp.begin(),dp.end());\n            for (int i=0;i<=r;i++){\n                if (i>=k) cp[i] = (1LL*(cp[i] + cp[i-k]))%MOD;\n            }\n            for (int i=r;i>=0;i--){\n                if (k>0){\n                    dp[i] = (cp[i] - (i-k*(v+1)>=0?cp[i-k*(v+1)]:0)+MOD)%MOD;\n                }\n                else{\n                    long t= (1LL*dp[i]*(v+1))%MOD;\n                    dp[i]=t;\n                }\n            }\n        }\n\n        int ans=0;\n        for (int i=l;i<=r;i++) ans = (ans + dp[i])%MOD;\n        return ans;\n        \n    }\n};\n```
['Dynamic Programming', 'C++']