c++ | dp
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nDynamic Programming\n\n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDynamic Programming\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(n)\n# Code\n```\n#define ll long long\n\nclass Solution \n{\npublic:\n    int numberOfUniqueGoodSubsequences(string binary) \n    {\n        int n=binary.size();\n        ll mod=1e9+7;\n        vector<ll> dp(n+9);\n        int s=0, f=0;\n        while( s<n &&  binary[s]==\'0\' ) s++, f=1;\n        dp[s++]=1;\n        vector<int> last(9, -1);\n\n        for(int i=s ;i<=n;i++ )\n        {\n            int x=binary[i-1]-\'0\';\n            if(x==0) f=1;\n            dp[i]=( dp[i-1]*2 )%mod;\n            if( last[x]>0 ) dp[i]=( dp[i]-dp[ last[x]-1 ] + mod ) % mod;\n            else if( x==0 ) dp[i]=( dp[i]-dp[s-1]+mod ) % mod;\n            last[x]=i;\n        }\n\n        if(!f)dp[n]=( dp[n]-1+mod )%mod;\n\n        return dp[n];\n\n    }\n};\n```
['C++']