【C++动态规划 子集状态压缩】2002. 两个回文子序列长度的最大乘积|1869
本文涉及知识点C++动态规划
位运算、状态压缩、罗列子集汇总
LeetCode2002. 两个回文子序列长度的最大乘积
给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何类似下标的字符，则它们是 不相交 的。
请你返回两个回文子序列长度可以到达的 最大乘积 。
子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读千篇同等，那么这个字符串是一个 回文字符串 。
示例 1：
https://i-blog.csdnimg.cn/direct/47d4fe6e953c458986c96ab242205cf2.png#pic_center
输入：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。
暴力一
罗列i,j，如果i&j则忽略。i,j ∈ \in ∈ 时间复杂度：O(4n)
暴力二
罗列i和 i的反码的子集。时间复杂度：O(3n)
动态规划+记忆化搜刮=错误
动态规划的状态表现
dp 表现s中，一个回文序列为k，另一个回文序列的长度。-2，表现未处理；-1，表现不存在长度为k的回文子序列。 空间复杂度：O(nnn)
动态规划的转移方程
len = j-i+1
如果len为1：
cur 代表dp，cur=1，别的为-1。
如果len为2：
dp=1 如果s= = s，则dp=2,否则d=1。别的全为-1。
如果len为3：
如果s= = s cur = dp+2
MaxSelf(cur,dp）
MaxSelf(cur,dp）
无论len是多少：
MaxSelf(cur],k)
时间复杂度：O(nnn)
动态规划的初始调用
Rec(0,N-1)
动态规划的返回值
dp.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;
if (-2 != cur)return;
const int len = j - i + 1;
if (1 == len) {
cur = 1;
}
else if (2 == len) {
cur = 1+(s == s);
cur = 1;
}
else {
Rec(i + 1, j - 1);
Rec(i , j - 1);
Rec(i + 1, j );
if (s == s)
{
for (int k = 0; k <= N; k++) {
cur = dp + 2;
}
}
for (int k = 0; k <= N; k++) {
cur = max(cur,dp );
cur = max(cur, dp);
}
}
vector<int> diff(N + 2);
for (int k = 0; k <= N; k++) {
for (int k1 = 0; k1 <= cur; k1++) {
cur = max(cur, k);
}
}
};
Rec(0, N - 1);
int ans = 0;
for (int i = 1; i < N; i++) {
ans = max(ans, dp.back() * 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 != tmp)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);
}
if (Is(tmp))m = tmp.size();
}
int ans = 1;
for (const auto& : 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);
}
}
}
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);
}
https://img-blog.csdnimg.cn/8d37dcd13ddb4df9af8f95fefd86828d.gif#pic_center#pic_center
扩展阅读
我想对大家说的话工作中碰到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。学习算法：按章节学习《喜缺全书算法册》，大量的标题和测试用例，打包下载。重视操纵有效学习：明确的目标 实时的反馈 拉伸区（难度符合） 专注闻缺陷则喜(喜缺)是一个优美的愿望，早发现问题，早修改问题，给老板节约钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙，那算法就是他的是睛失败+反思=成功 成功+反思=成功 视频课程
先学简单的课程，请移步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++**实现。
https://img-blog.csdnimg.cn/f95ddae62a4e43a68295601c723f92fb.gif#pic_center
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]