C++ bottom-up DP mask
Let dp[mask] denotes the longest length of palindromic subsequence in the string "mask" specifies. For example, mask = "11010", s = "abcad", mask has the sequen
Let dp[mask] denotes the longest length of palindromic subsequence in the string "mask" specifies. For example, mask = "11010", s = "abcad", mask has the sequence of "a, b, a", and dp[mask] = 3; other code is exactly to find the longest length of palindromic. \n\n\n\'\'\'\n\n        int maxProduct(string s) {\n\t\t\tint n = s.size();\n\t\t\tvector<int> dp(1<<n, 0);\n\t\t\t//calculated only one letter in the subsequence, it obviously equals to 1.\n\t\t\tfor (int i = 0; i < n; i++) {\n\t\t\t\tdp[1<<i] = 1;\n\t\t\t}\n\t\t\tfor (int mask = 1; mask < (1 << n); mask++) {\n\t\t\t\tint left = 0, right = 0;\n\t\t\t\tfor (int i = 0; i < n; i++) {\n\t\t\t\t\tif (mask & (1 << i)) {\n\t\t\t\t\t\tleft = i;\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tfor (int i = n - 1; i >= 0; i--) {\n\t\t\t\t\tif (mask & (1 << i)) {\n\t\t\t\t\t\tright = i;\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\t//we must make sure mask has at least two "1", since only one "1" is calculated.\n\t\t\t\tif (left == right) continue;\n\n\t\t\t\tint newmask = mask - (1<<left) - (1 << right);\n\t\t\t\tif (s[left] == s[right]) dp[mask] = dp[newmask] + 2;\n\t\t\t\telse {\n\t\t\t\t\tdp[mask] = max(dp[mask - (1<<left)], dp[mask - (1<<right)]);\n\t\t\t\t}\n\t\t\t}\n\t\t\tint res = -1;\n\t\t\tint allones = (1<<n) - 1;\n\t\t\tfor (int mask = 1; mask < (1 << n); mask++) {\n\t\t\t\tres = max(res, dp[mask] * dp[allones - mask]);\n\t\t\t}\n\t\t\treturn res;\n    }\n\n\n\'\'\'
[]