Nice optimisation trick on Coin Change Problem ( using 2 dp)
Intuition\nFirst Observation one need to make is that # of distint element in array cannot exceed 200.\nUsing this observation we will make our dp (similar to c
# Intuition\nFirst Observation one need to make is that # of distint element in array cannot exceed 200.\nUsing this observation we will make our dp (similar to coin change)\nlet dp[i][sumleft]=no of ways make Sumleft using index (i---n-1)\n# Approach\n Let\'s move to transitions\n dp[i][sumleft]=dp[i+1][sumleft] // don\'t include current element \n dp[i][sumleft]=dp[i+1][sumleft-j*(nums[i])] // where j varies from 1 to occ(nums[i])\nNote: having above transition and states will avoid overcounting as dp will consider each group of same nums[i] as an single unit , so contribution from each nums[i] will only depend on different occurance of it taken in dp \n\nNow coming to optimising the transition ( without it it will tle because worst case complexity is O(200*n*r)), so lets make another dp array named dp2, which will store the sum of values of transitions i.e dp2[i][sleft]=(dp1[i+1][sleft-nums[i]]+dp2[i+1][sleft-nums[i]*2]+.....+dp[i+1][sleft%nums[i]])\nUsing this dp2 array we can now write transitions for original dp as \ndp[i][sleft]=(dp[i][sleft]+dp2[i+1][sleft]-dp2[i+1][(sleft-(occ(nums[i]))*nums[i])])\n\nYou can try implementing it, or refer to the code. \n\n# Complexity\n- Time complexity:\n  O(no_of_distinct(nums[i])*r)\n- Space complexity:\n  O(200*sum)\n\n# Code\n```\nconst int mod=1e9+7;\nvector<pair<int,int>>v;\nint dp1[201][20010];\nint dp2[201][20010];\nint n;\n int rec(int level,int sleft);\n    int go(int level,int sleft){\n        if(sleft<0) return 0;\n        if(dp2[level][sleft]!=-1) return dp2[level][sleft];\n        int ans=(go(level,sleft-v[level-1].first)+rec(level,sleft-v[level-1].first))%mod;\n        return dp2[level][sleft]=ans;\n    }\n    int rec(int level,int sleft){\n        if(sleft<0) return 0;\n        if(level==n){\n            if(sleft) return 0;\n            return 1;\n        }\n        auto &ans=dp1[level][sleft];\n        if(ans!=-1) return ans;\n        if(v[level].first){\n        ans=(rec(level+1,sleft)+go(level+1,sleft))%mod;\n        ans-=(go(level+1,sleft-(v[level].first*(v[level].second))));\n        ans%=mod;\n        if(ans<0) ans+=mod;\n        }\n        else ans=(1ll*rec(level+1,sleft)*(v[level].second+1))%mod; // handle case for 0 o/w infinite recursion (go )\n        return ans;\n    }\nclass Solution {\npublic:\n   \n    int countSubMultisets(vector<int>& nums, int l, int r) {\n       int sum=0;\n       map<int,int>mp;\n       for(auto i:nums) sum+=i,mp[i]++;\n       n=mp.size();\n       v.clear();\n       for(auto i:mp) v.push_back({i.first,i.second});\n       r=min(r,sum);\n       for(int i=0;i<=n;i++){\n           for(int j=0;j<=r;j++) dp1[i][j]=dp2[i][j]=-1;\n       }\n       int ans=0;\n       for(int i=l;i<=r;i++){\n           ans=(ans*1ll+rec(0,i))%mod;\n       }\n       return ans;\n    }\n};\n```
['C++']