Hard DP | python
Approach\nThe number of different numbers is at most $\sqrt n$ so we can iterate over all the different numbers and make a DP , the problem here is that even th
# Approach\nThe number of different numbers is at most $\\sqrt n$ so we can iterate over all the different numbers and make a DP , the problem here is that even the different numbers are relatively small, we still have to update the DP in a clever way in order to reduce the complexity.\n\nThe $DP$ transitions are:\n\n$DP[start +w \\times i]+= \\sum OldDP[start + w \\times i]$.\n\n$OldDP$ is just the state of the $DP$ one step before, i.e in the last $w$ ,we do it to save memory.\n\nWe have to iterate over all possible $start$ and then update the multiples of $w$ for each unique number while the multiple not pass the maximum sum called $N$.\n\n\nwith $DP[0] = freq[0]+1$.\n\nI can explain it better later if supported but for now I leave the code.\n\nI also have to say that in c++ I could not solve it because of the overflow.\n\n# Complexity\n-  $O(n \\times \\sqrt(n))$\n# Code\n```\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        N = 0\n        for c  in nums:\n            N+=c\n        \n        freq = [0]*(N+1)\n        for c in nums:\n            freq[c]+=1\n\n            \n        compressed =[]\n        \n        for i in range(1,N+1):\n            if freq[i] > 0 :\n                compressed.append((i, freq[i]))\n\n        \n        dp = [0]*(N+1)\n        dp[0] = freq[0]+1\n        mod = 10**9 + 7\n        \n        for w,k in compressed:\n            ndp = dp.copy()\n            \n            for p in range(w):\n                sum = 0\n                \n                multiple = p\n                count = 0\n                while multiple <=N:\n                    if (count > k):\n                        sum -= dp[multiple - (w * count)]\n                        count-=1\n\n                    ndp[multiple] += sum\n                    sum += dp[multiple]\n                    multiple+=w\n                    count+=1\n\n            dp,ndp = (ndp,dp)\n        \n        ans = 0\n        for i in range(l,min(N+1,r+1)):\n            ans+=dp[i]\n            ans%=mod\n            \n        return ans\n        \n        \n```
['Python3']