C++ Clean DP Solution with Explanation time:O(n) space:O(1)
dp[i][j] denote the number of distinct subsequences starting with \'i\' and end with \'j\'\nHere\'s the dp transition:\nCase \'0\':\nIf the current character is
```dp[i][j]``` denote the number of distinct subsequences starting with \'i\' and end with \'j\'\nHere\'s the dp transition:\n**Case \'0\':**\nIf the current character is \'0\', since we are counting distinct subsequences and there shouldn\'t be any leading zeros in the subsequences, we set ```dp[0][0] = 1```, ex: string "000000" only have a subsequence \'0\'\n```dp[1][0] = dp[1][0] + dp[1][1]``` because it will be the number of ways that we add a \'0\' to a subsequence starting with \'1\' and ends with either \'0\' or \'1\'\n\n**Case \'1\':**\nIf the current character is \'1\', since we can\'t have leading zeros, ```dp[0][1]``` is always 0 ("0001" is not a valid subsequence)\nThe transition will be ```dp[1][1] = dp[1][0] + dp[1][1] + 1```. As we can see, ```dp[1][0] + dp[1][1]``` part is same as the case ending with zero. Since we append a \'1\' to every subsequence ```dp[1][0]``` and ```dp[1][1]```, we are missing the subsequence "1" with length 1; therefore, we add a one to it.\n\nNote that all calculation above should be done with modulo.\n\nTime Complexity: O(n)\nSpace Complexity: O(1)\n\n```\ntypedef int64_t ll;\n\nclass Solution {\npublic:\n    int numberOfUniqueGoodSubsequences(string s) {\n        const int mod = 1e9 + 7;\n        ll dp[2][2] = {};\n        for(char c : s) {\n            int a = c - \'0\';\n            if(a == 0) {\n                dp[0][0] = 1;\n                dp[1][0] = (dp[1][0] + dp[1][1]) % mod;\n            } else {\n                dp[1][1] = (dp[1][0] + dp[1][1] + 1) % mod;\n            }\n        }\n        return (dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]) % mod;\n    }\n};\n```\nPlease upvote!
['Dynamic Programming', 'C']