【C++动态规划 子集状态压缩】2002. 两个回文子序列长度的最大乘积|1869 ...

本文涉及知识点

C++动态规划
位运算、状态压缩、罗列子集汇总
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(4n)
暴力二

罗列i和 i的反码的子集。时间复杂度：O(3n)
动态规划+记忆化搜刮=错误

动态规划的状态表现

dp[j][k] 表现s[i…j]中，一个回文序列为k，另一个回文序列的长度。-2，表现未处理；-1，表现不存在长度为k的回文子序列。 空间复杂度：O(nnn)
动态规划的转移方程

len = j-i+1
如果len为1：
cur 代表dp[j]，cur[0]=1，别的为-1。
如果len为2：
dp[1]=1 如果s= = s[j]，则dp[0]=2,否则d[0]=1。别的全为-1。
如果len为3：
如果s= = 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

1. class Solution {
2.                 public:
3.                         int maxProduct(string s) {
4.                                 const int N = s.length();
5.                                 vector<vector<vector<int>>> dp(N, vector<vector<int>>(N,vector<int>(N+1,-2)));
6.                                 function<void(int, int)> Rec = [&](int i, int j) {
7.                                         auto& cur = dp[i][j];
8.                                         if (-2 != cur[0])return;
9.                                         const int len = j - i + 1;
10.                                         if (1 == len) {
11.                                                 cur[0] = 1;
12.                                         }
13.                                         else if (2 == len) {
14.                                                 cur[0] = 1+(s[i] == s[j]);
15.                                                 cur[1] = 1;
16.                                         }
17.                                         else {
18.                                                 Rec(i + 1, j - 1);
19.                                                 Rec(i , j - 1);
20.                                                 Rec(i + 1, j );
21.                                                 if (s[i] == s[j])
22.                                                 {
23.                                                         for (int k = 0; k <= N; k++) {                                                               
24.                                                                 cur[k] = dp[i + 1][j - 1][k] + 2;
25.                                                         }
26.                                                 }
27.                                                 for (int k = 0; k <= N; k++) {
28.                                                         cur[k] = max(cur[k],dp[i+1][j][k] );
29.                                                         cur[k] = max(cur[k], dp[i][j-1][k]);
30.                                                 }
31.                                         }
32.                                         vector<int> diff(N + 2);
33.                                         for (int k = 0; k <= N; k++) {
34.                                                 for (int k1 = 0; k1 <= cur[k]; k1++) {
35.                                                         cur[k1] = max(cur[k1], k);
36.                                                 }
37.                                         }
38.                                 };
39.                                 Rec(0, N - 1);
40.                                 int ans = 0;
41.                                 for (int i = 1; i < N; i++) {
42.                                         ans = max(ans, dp[0].back()[i] * i);
43.                                 }
44.                                 return ans;
45.                         }
46.                 };

复制代码

暴力二代码

核心代码

1. class Solution {
2.                 public:
3.                         int maxProduct(string s) {
4.                                 const int N = s.length();
5.                                 const int MC = 1 << N;
6.                                 auto Is = [&](const vector<int>& tmp) {
7.                                         for (int i = 0; i < tmp.size() / 2; i++) {
8.                                                 if (tmp[i] != tmp[tmp.size() - 1 - i])return false;
9.                                         }
10.                                         return true;
11.                                 };
12.                                 unordered_map<int, int> m;
13.                                 for (int i = 0; i < MC; i++) {
14.                                         vector<int> tmp;
15.                                         for (int j = 0; j < N; j++) {
16.                                                 if (i & (1 << j))tmp.emplace_back(s[j]);
17.                                         }
18.                                         if (Is(tmp))m[i] = tmp.size();
19.                                 }
20.                                 int ans = 1;
21.                                 for (const auto& [i, l1] : m) {
22.                                         const int remain = i ^ (MC - 1);
23.                                         for (int j = remain; j; j = (j - 1) & remain) {
24.                                                 if (m.count(j)) {
25.                                                         ans = max(ans, l1 * m[j]);
26.                                                 }
27.                                         }
28.                                 }       
29.                                 return ans;
30.                         }
31.                 };

复制代码

单位测试

1. TEST_METHOD(TestMethod1)
2.                 {
3.                         string s = "bab";
4.                         auto res = Solution().maxProduct(s);
5.                         AssertEx(2, res);
6.                 }
7.                 TEST_METHOD(TestMethod2)
8.                 {
9.                         string s = "eetcodec";
10.                         auto res = Solution().maxProduct(s);
11.                         AssertEx(9, res);
12.                 }
13.                 TEST_METHOD(TestMethod11)
14.                 {
15.                         string s = "leetcodecom";
16.                         auto res = Solution().maxProduct(s);
17.                         AssertEx(9, res);
18.                 }
19.                 TEST_METHOD(TestMethod12)
20.                 {
21.                         string s = "bb";
22.                         auto res = Solution().maxProduct(s);
23.                         AssertEx(1, res);
24.                 }       
25.                 TEST_METHOD(TestMethod13)
26.                 {
27.                         string s = "accbcaxxcxx";
28.                         auto res = Solution().maxProduct(s);
29.                         AssertEx(25, res);
30.                 }

复制代码

扩展阅读

我想对大家说的话工作中碰到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。学习算法：按章节学习《喜缺全书算法册》，大量的标题和测试用例，打包下载。重视操纵有效学习：明确的目标 实时的反馈 拉伸区（难度符合） 专注闻缺陷则喜(喜缺)是一个优美的愿望，早发现问题，早修改问题，给老板节约钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙，那算法就是他的是睛失败+反思=成功 成功+反思=成功 视频课程

先学简单的课程，请移步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++**实现。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。