本文涉及知识点
LeetCode2002. 两个回文子序列长度的最大乘积
给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。
请你返回两个回文子序列长度可以达到的 最大乘积 。
子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串 。
示例 1：
输入：s = “leetcodecom”
输出：9
解释：最优方案是选择 “ete” 作为第一个子序列，“cdc” 作为第二个子序列。
它们的乘积为 3 * 3 = 9 。
示例 2：
输入：s = “bb”
输出：1
解释：最优方案为选择 “b” （第一个字符）作为第一个子序列，“b” （第二个字符）作为第二个子序列。
它们的乘积为 1 * 1 = 1 。
示例 3：
输入：s = “accbcaxxcxx”
输出：25
解释：最优方案为选择 “accca” 作为第一个子序列，“xxcxx” 作为第二个子序列。
它们的乘积为 5 * 5 = 25 。
提示：
2 <= s.length <= 12
s 只含有小写英文字母。
暴力
v记录所有回文子序列的掩码mask和子系列的长度。（1<<j)&mask 表示此子序列是否包括s[j]。
暴力一
枚举i,j，如果i&j则忽略。i,j ∈ \in ∈[v] 时间复杂度：O(4)
暴力二
枚举i和 i的反码的子集。时间复杂度：O(3)
动态规划+记忆化搜索=错误
动态规划的状态表示
dp[i][j][k] 表示s[i…j]中，一个回文序列为k，另一个回文序列的长度。-2，表示未处理；-1，表示不存在长度为k的回文子序列。 空间复杂度：O(nnn)
动态规划的转移方程
len = j-i+1
如果len为1：
cur 代表dp[i][j]，cur[0]=1，其它为-1。
如果len为2：
dp[1]=1 如果s[i]= = s[j]，则dp[0]=2,否则d[0]=1。其它全为-1。
如果len为3：
如果s[i]= = s[j] cur[k] = dp[i+1][j-1][k]+2
MaxSelf(cur[k],dp[i+1][j][k]）
MaxSelf(cur[k],dp[i ][j-1][k]）
无论len是多少：
MaxSelf(cur[cur[k]],k)
时间复杂度：O(nnn)
动态规划的初始调用
Rec(0,N-1)
动态规划的返回值
dp[0].back() 值乘以下标的最大值。
错误代码
本解法的假设：最外围的回文对，一定包括所有的回文。比如：AXXYYA
实际上可能是：ABAB ,可以拆分出：AA BB
class Solution {
public:
int maxProduct(string s) {
const int N = s.length();
vector<vector<vector<int>>> dp(N, vector<vector<int>>(N,vector<int>(N+1,-2)));
function<void(int, int)> Rec = [&](int i, int j) {
auto& cur = dp[i][j];
if (-2 != cur[0])return;
const int len = j - i + 1;
if (1 == len) {
cur[0] = 1;
}
else if (2 == len) {
cur[0] = 1+(s[i] == s[j]);
cur[1] = 1;
}
else {
Rec(i + 1, j - 1);
Rec(i , j - 1);
Rec(i + 1, j );
if (s[i] == s[j])
{
for (int k = 0; k <= N; k++) {
cur[k] = dp[i + 1][j - 1][k] + 2;
}
}
for (int k = 0; k <= N; k++) {
cur[k] = max(cur[k],dp[i+1][j][k] );
cur[k] = max(cur[k], dp[i][j-1][k]);
}
}
vector<int> diff(N + 2);
for (int k = 0; k <= N; k++) {
for (int k1 = 0; k1 <= cur[k]; k1++) {
cur[k1] = max(cur[k1], k);
}
}
};
Rec(0, N - 1);
int ans = 0;
for (int i = 1; i < N; i++) {
ans = max(ans, dp[0].back()[i] * i);
}
return ans;
}
};
暴力二代码
核心代码
class Solution {
public:
int maxProduct(string s) {
const int N = s.length();
const int MC = 1 << N;
auto Is = [&](const vector<int>& tmp) {
for (int i = 0; i < tmp.size() / 2; i++) {
if (tmp[i] != tmp[tmp.size() - 1 - i])return false;
}
return true;
};
unordered_map<int, int> m;
for (int i = 0; i < MC; i++) {
vector<int> tmp;
for (int j = 0; j < N; j++) {
if (i & (1 << j))tmp.emplace_back(s[j]);
}
if (Is(tmp))m[i] = tmp.size();
}
int ans = 1;
for (const auto& [i, l1] : m) {
const int remain = i ^ (MC - 1);
for (int j = remain; j; j = (j - 1) & remain) {
if (m.count(j)) {
ans = max(ans, l1 * m[j]);
}
}
}
return ans;
}
};
单元测试
TEST_METHOD(TestMethod1)
{
string s = "bab";
auto res = Solution().maxProduct(s);
AssertEx(2, res);
}
TEST_METHOD(TestMethod2)
{
string s = "eetcodec";
auto res = Solution().maxProduct(s);
AssertEx(9, res);
}
TEST_METHOD(TestMethod11)
{
string s = "leetcodecom";
auto res = Solution().maxProduct(s);
AssertEx(9, res);
}
TEST_METHOD(TestMethod12)
{
string s = "bb";
auto res = Solution().maxProduct(s);
AssertEx(1, res);
}
TEST_METHOD(TestMethod13)
{
string s = "accbcaxxcxx";
auto res = Solution().maxProduct(s);
AssertEx(25, res);
}
扩展阅读
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。