Python DP From Naive to Optimized
Start off with the most naive approach(TLE)\n\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        # dp[i]: good subsequ
Start off with the most naive approach(TLE)\n```\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        # dp[i]: good subsequences of binary[:i+1]\n\t\t\n        n = len(binary)\n        dp = [set(binary[i]) for i in range(n)]\n        \n        for i in range(n):\n            cur = binary[i]\n            for j in range(i):\n                for good in dp[j]:\n                    if good[0] != \'0\':\n                        dp[i].add(good + cur)\n                        \n        return len(set.union(*dp))\n```\nOptimize dp from O(n^2) to O(n) since it\'s the same as adding new subsequences to the same set(TLE)\n```\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        n = len(binary)\n        dp = set(binary[0])\n\n        for i in range(1, n):\n            for good in set(dp):\n                if good[0] != \'0\':\n                    dp.add(good + binary[i])\n            dp.add(binary[i])\n        \n        return len(dp)\n```\nDP over number instead of strings\n```\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        # Set was used because there can be duplicates when we\n        # go from, e.g. [1, 11] to [1, 11, 111]\n        # 1 -> 11\n        # 11 -> 111\n        # [1, 11, 11, 111] -> [1, 11, 111]\n        # However, the unique subsequences can be recorded as\n        # number of sequences instead:\n        # [1, 11] -> [1, 11, 111]\n        # =>\n        # 1 + len[11, 111] = 3\n        \n        # But that\'s only the case of a trailing one, when we meet\n        # a zero, we do not need to add one becuase we don\'t need\n        # to add the single 1 ahead.\n        \n        # And that will not work with a single dp field, because\n        # the new values computed are classified as either trailing\n        # 0 or 1, so the strategy is:\n        \n        # if binary[i] == \'1\':\n        #     dp_ones = dp_ones + dp_zeros + 1\n        # else:\n        #     dp_zeros = dp_ones + dp_zeros\n        \n        # And that ignores the exception case of a single "0",\n        # so add 1 to the result if "0" is present.\n        \n        mod = 10 ** 9 + 7\n        zeros, ones = 0, 0\n        \n        for i in binary:\n            if i == \'1\':\n                ones += zeros + 1\n                ones %= mod\n            else:\n                zeros += ones\n                zeros %= mod\n\n        return (zeros + ones + (\'0\' in binary)) % mod\n```
[]