【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

classSolution{public:intmaxProduct(string s){constint 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;constint len = j - i +1;if(1== len){ cur[0]=1;}elseif(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;}};

暴力二代码

核心代码

classSolution{public:intmaxProduct(string s){constint N = s.length();constint 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])returnfalse;}returntrue;}; 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(constauto&[i, l1]: m){constint 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);}

扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。