[Python] True O(2^n) dp on subsets solution, explained
I saw several dp solution, which states that they have O(2^n) complexity, but they use bit manipulations, such as looking for first and last significant bit, wh
I saw several `dp` solution, which states that they have `O(2^n)` complexity, but they use bit manipulations, such as looking for first and last significant bit, which we can not say is truly `O(1)`. So I decided to write my own **true** `O(2^n)` solution.\n\nLet `dp(mask)` be the maximum length of palindrome if we allowed to use only non-zero bits from `mask`. In fact, this means, if we have `s = leetcode` and `mask = 01011001`, we can use only `etce` subsequence. How to evaluate `dp(mask)`?\n\n1. First option is we do not take last significant one, that is we work here with `01011000` and ask what is answer for this mask.\n2. Second option is we do not take first significant bit, that is we work here with `00011001` mask here.\n3. Final option is to take both first and last significant bits but it is allowed only if we have equal elements for them, that is we have mase `00011000` here and because `s[1] = s[7]` we can take this option.\n\nAlso what I calclate all first and last significant bits for all numbers in range `1, 1<<n`.\n\n#### Complexity\nTime complexity is `O(2^n)`, space complexity also `O(2^n)` to keep `dp` cache and `last` and `first` arrays.\n\n```python\nclass Solution:\n    def maxProduct(self, s):\n        n = len(s)\n        \n        first, last = [0]*(1<<n), [0]*(1<<n)\n        \n        for i in range(n):\n            for j in range(1<<i, 1<<(i+1)):\n                first[j] = i\n\n        for i in range(n):\n            for j in range(1<<i, 1<<n, 1<<(i+1)):\n                last[j] = i\n        \n        @lru_cache(None)\n        def dp(m):\n            if m & (m-1) == 0: return m != 0\n            l, f = last[m], first[m]\n            lb, fb = 1<<l, 1<<f\n            return max(dp(m-lb), dp(m-fb), dp(m-lb-fb) + (s[l] == s[f]) * 2)\n       \n        ans = 0\n        for m in range(1, 1<<n):\n            ans = max(ans, dp(m)*dp((1<<n) - 1 - m))\n            \n        return ans\n```\n\nIf you have any questoins, feel free to ask. If you like the solution and explanation, please **upvote!**
['Dynamic Programming']