【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(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);}

扩展阅读

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