Easily Provable bottom-up DP in Python, O(n) Time, O(1) Space (With proper explanation)
Intuition\nWe let dp[i] be the number of unique subsequences starting with binary[i]\n\nObserve that there are 3 disjoint types of subsequences starting with bi
# Intuition\nWe let `dp[i]` be the number of unique subsequences starting with `binary[i]`\n\nObserve that there are 3 disjoint types of subsequences starting with `binary[i]`\n- The singleton sequence `binary[i]`: type 1\n- Sequences that start with `binary[i]`, with second character `0`: type 2\n- Sequences that stat with `binary[i]`, with second character `1`: type 3\n\nWe let \n- `nZero[i]` be the index of the smallest `j > i` such that `binary[j] = 0`\n- `nOne[i]` be the index of the smallest `j > i` such that `binary[j] = 1`\n\nObserve that\n- The number of type 1 subsequences is always 1\n- The number of type 2 subsequences is `dp[nZero[i]]`\n    - This is because if the second character is 0, we can greedily assume that this 0 comes from the **first** 0 on the right of `binary[i]`\n    - Consider any constructible subsequence with `binary[i]` as the first digit and a 0 as the second digit. If this 0 came from `binary[k]` where `k > nZero[i]`, we could also construct this same subsequence by keeping the same digits selected but taking `binary[nZero[i]` rather than `binary[k]`\n- The number of type 3 subsequences is `dp[nOne[i]]`\n    - With symmetric reasoning\n    \nSince the 3 types of subsequences are mutually exclusive and mutually exhaustive:\n```dp[i] = 1 + dp[nZero[i]] + dp[nOne[i]]```\n\nThe answer is then `dp[i]` where `i` is the index of the leftmost 1. We also need to add back 1 if there is a 0 in the array. \n\n# Approach\nThis problem is suitable to be dealt with in a bottom-up manner since if we deal with the list from right to left, we can compute `nZero[i]` and `nOne[i]` on the fly and avoid having to store those arrays separately.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(1)$$\n\n# Code\n```\nMOD = int(1e9+7)\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        n = len(binary)\n        nZero = None\n        nOne = None\n\n        dp = [0 for _ in range(n)]\n        for i in range(n-1, -1, -1):\n            dp[i] = 1 + (0 if not nZero else a[nZero]) + (0 if not nOne else a[nOne])\n            dp[i] %= MOD\n\n            if binary[i] == \'0\': nZero = i\n            else: nOne = i\n            \n        ans = 0\n        if nOne is not None: ans = dp[nOne] # most significant one\n        if nZero is not None: ans += 1\n        return ans\n```
['Dynamic Programming', 'Python3']