C++ DP from O(3^N) to O(2^N)
See my latest update in repo LeetCode\n\n## Solution 1. Bitmask DP\n\nLet dp[mask] be the length of the longest palindromic subsequence within the subsequence r
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Bitmask DP\n\nLet `dp[mask]` be the length of the longest palindromic subsequence within the subsequence represented by `mask`.\n\nThe answer is `max( dp[m] * dp[(1 << N) - 1 - m] | 1 <= m < 1 << N )`. (`(1 << N) - 1 - m)` is the complement subset of `m`.\n\nFor `dp[m]`, we can brute-forcely enumerate each of its subset, and compute the maximum length of its palindromic subsets.\n\n```\ndp[m] = max( bitcount( sub ) | `sub` is a subset of `m`, and `sub` forms a palindrome )\n```\n\n```cpp\n// OJ: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/\n// Author: github.com/lzl124631x\n// Time: O(N * 2^N + 3^N)\n// Space: O(2^N)\nclass Solution {\n    bool isPalindrome(string &s, int mask) {\n        vector<int> index;\n        for (int i = 0; mask; mask >>= 1, ++i) {\n            if (mask & 1) index.push_back(i);\n        }\n        for (int i = 0, j = index.size() - 1; i < j; ++i, --j) {\n            if (s[index[i]] != s[index[j]]) return false;\n        }\n        return true;\n    }\npublic:\n    int maxProduct(string s) {\n        int N = s.size();\n        vector<int> dp(1 << N), pal(1 << N);\n        for (int m = 1; m < 1 << N; ++m) {\n            pal[m] = isPalindrome(s, m);\n        }\n        for (int m = 1; m < 1 << N; ++m) { // `m` is a subset of all the characters\n            for (int sub = m; sub; sub = (sub - 1) & m) { // `sub` is a subset of `m`\n                if (pal[sub]) dp[m] = max(dp[m], __builtin_popcount(sub)); // if this subset forms a palindrome, update the maximum length\n            }\n        }\n        int ans = 0;\n        for (int m = 1; m < 1 << N; ++m) {\n            ans = max(ans, dp[m] * dp[(1 << N) - 1 - m]);\n        }\n        return ans;\n    }\n};\n```\n\n## Solution 2. Bitmask DP\n\nIn Solution 1, filling the `pal` array takes `O(N * 2^N)` time. We can reduce the time to `O(2^N)` using DP.\n\n```\npal[m] = s[lb] == s[hb] && pal[x]\n         where `lb` and `hb` are the indexes of the lowest and highest bits of `m`, respectively,\n            and `x` equals `m` removing the lowest and highest bits.\n```\n\n```cpp\nvector<bool> pal(1 << N);\npal[0] = 1;\nfor (int m = 1; m < 1 << N; ++m) {\n    int lb = __builtin_ctz(m & -m), hb = 31 - __builtin_clz(m); \n    pal[m] = s[lb] == s[hb] && pal[m & ~(1 << lb) & ~(1 << hb)];\n}\n```\n\nUsing the same DP idea, we can reduce the time complexity for filling the `dp` array from `O(3^N)` to `O(2^N)`, and we don\'t even need the `pal` array.\n\n```\n// if `m` is only a single bit 1\ndp[m] = 1 \n\n// otherwise\ndp[m] = max( \n                dp[m - (1 << lb)], // if we exclude `s[lb]`\n                dp[m - (1 << hb)], // if we exclude `s[hb]`\n                dp[m - (1 << lb) - (1 << hb)] + (s[lb] == s[hb] ? 2 : 0) // If we exclude both `s[lb]` and `s[hb]` and plus 2 if `s[lb] == s[hb]`\n            )\n```\n\n```cpp\n// OJ: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/\n// Author: github.com/lzl124631x\n// Time: O(2^N)\n// Space: O(2^N)\nclass Solution {\npublic:\n    int maxProduct(string s) {\n        int N = s.size();\n        vector<int> dp(1 << N);\n        for (int m = 1; m < 1 << N; ++m) {\n            if (__builtin_popcount(m) == 1) dp[m] = 1; \n            else {\n                int lb = __builtin_ctz(m & -m), hb = 31 - __builtin_clz(m);\n                dp[m] = max({ dp[m - (1 << lb)], dp[m - (1 << hb)], dp[m - (1 << lb) - (1 << hb)] + (s[lb] == s[hb] ? 2 : 0) });\n            }\n        }\n        int ans = 0;\n        for (int m = 1; m < 1 << N; ++m) {\n            ans = max(ans, dp[m] * dp[(1 << N) - 1 - m]);\n        }\n        return ans;\n    }\n};\n```
[]