[Python] Dynamic Programming with thought process when being asked during interviews
Dynamic Programming\nOnce you see the answer might be very large, 99% of possibility resolving this promble is to use dynamic programming.\nLet\'s simplify the 
### Dynamic Programming\nOnce you see the answer might be very large, 99% of possibility resolving this promble is to use dynamic programming.\nLet\'s simplify the question first without considering unique requirement, how to find out the number of good subsequences at index `i` given the number of good subsequences at index `i - 1`. \nWe know that `1` can construct new good subsequences, while `0` doesn\'t. So if index `i` is `1` then the `dp[i] = dp[i - 1] * 2 + 1`. Why? because we can append `1` to each of good subsequence we got from `dp[i - 1]`, as well as the single `1` at index `i`. \n\nOtherwise `dp[i] = dp[i - 1] * 2` for `0` since leading `0` is invalid for good subsequences.\nThen the next step is the difficult part, how about adding unique back?\nNow we have the total number of good subsequences with duplicates, in order to get the unique, we have to remove the duplicate, literally `dp[i] = dp[i] - dup`.\nSo now the problem changes to be how many duplicate subsequences we add by appending `1` or `0`?\nWe can assume there is no dup in `dp[i -1]` and so we can only care about the dup introduced by appending index `i`. Let\'s simpilfy the problem first by considering `1` only since `0` followes the same idea. \nThe intuitive thought is that in order to have dup, the `1` at index `i` can replace the last seen `1` at index `k`. There must be subsequences including `1` at index `k`, and those without index `k`. \nNow we append `1` after those without index `k` as if we didn\'t pick the `1` at index `k` but picked `1` at index `i` instead.\nfor example, `1011` and we are looking at the last `1`, where we have subsequences\n```\n1\n10\n101\n11\n```\nwith  `1` and `10` being without the `1` at index 2.\nThen we append `1` at index 3, then `10 + 1= 101, 1 + 1 = 11` which are equal to append `1` at index 2 to `1` and `10`, the number of good subsequences added by appending index 2. \nalright, then what about the last single `1` introduced by index 3? it\'s equals to consider the `1` at index 0. \nFinally, it turns out to be the number  of dup is equal to the sum of number of subsequences added by appending each `1` appeared before index `i`.\nSo the transition is \n```\ndp[i] = dp[i] * 2 + 1 - sum(diff[...i] for k in nums if k == 1) when nums[i] == 1\ndp[i] = dp[i] * 2 - sum(diff[...i] for k in nums if k== 0) when nums[i] == 0\n```\n\n```python\ndef numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n\tzero_diff = one_diff = count = 0\n\tfor c in binary:\n\t\tprev, count = count, count * 2\n\t\tif c == \'1\':\n\t\t\tcount += 1 - one_diff\n\t\t\tone_diff += count - prev\n\t\telse:    \n\t\t\tcount -= zero_diff\n\t\t\tzero_diff += count - prev\n\t\tcount %= 10 ** 9 + 7      \n\treturn count + int(\'0\' in binary)\n```\n\n*Time Complexity*= **O(N)**\n*Space Complexity*= **O(1)**\n
['Dynamic Programming', 'Python']