最长回文串子序列
方法一
做这道题目我们其实可以复用下上面的最长公共子序列的代码来做
我们可以将字符串逆序一下创造出一个新的字符串
再找出这两个字符串的最长公共子序列 我们找出来的最长公共子序列就是回文子序列 （其实我们可以想想两个指针从一个字符串的两端开始查找）
方法二
递归版本
我们写的递归函数如下
int process(string& str , int L , int R)
它的含义是 我们给定一个字符串str 返回给这个字符串从L到R位置上的最大回文子串
参数含义如下
- str 我们需要知道回文子串长度的字符串
- L 我们需要知道回文子串长度的起始位置
- R 我们需要知道回文子串长度的终止位置
所有的递归函数都一样 我们首先来想base case
这道题目中变化的参数其实就只有L 和 R 所以说我们只需要考虑L和R的base case
如果L和R相等 如果L和R只相差1
if (L == R) { return 1; } if (L == R - 1) { return str[L] == str[R] ? 2 : 1; }
之后我们来考虑下普遍的可能性
- 如果L 和 R就是回文子序列的一部分
- 如果L可能是回文子序列的一部分 R不是
- 如果L不是回文子序列的一部分 R有可能是
我们按照上面的可能性分析写出下面的代码 之后返回最大值即可
int p1 = process(str , L + 1 , R); int p2 = process(str , L , R - 1); int p3 = str[L] == str[R] ? 2 + process(str , L + 1, R - 1) : 0; return max(max(p1 , p2) , p3);
动态规划
我们注意到原递归函数中 可变参数只有L 和 R 所以说我们只需要围绕着L 和 R建立一张二维表就可以
当然 在一般情况下 L是一定小于等于R的 所以说L大于R的区域我们不考虑
我们首先来看base case
if (L == R) { return 1; } if (L == R - 1) { return str[L] == str[R] ? 2 : 1; }
围绕着这个base case 我们就可以填写两个对角线的内容
for (int L = 0; L < str.size(); L++) { for(int R = L; R < str.size(); R++) { if (L == R) { dp[L][R] = 0; } if (L == R-1) { dp[L][R-1] = str[L] == str[R] ? 2 : 1; } } }
接下来我们看一个格子普遍依赖哪些格子
int p1 = process(str , L + 1 , R); int p2 = process(str , L , R - 1); int p3 = str[L] == str[R] ? 2 + process(str , L + 1, R - 1) : 0;
从上面的代码我们可以看到 分别依赖于
L+1 R L , R-1 L+1 , R-1
从图上来分析 黑色的格子依赖于三个红色格子
于是我们就可以沿着对角线来不断的填写数字
横行一直从0开始 纵列一直在变化 所以我们用列来遍历
最后返回dp[0][str.size()-1]即可
int process1(string& str , vector<vector<int>>& dp) { for (int L = 0; L < str.size(); L++) { for(int R = 0; R < str.size(); R++) { if (L == R) { dp[L][R] = 1; } if (L == R-1) { dp[L][R] = str[L] == str[R] ? 2 : 1; } } } for (int startR = 2; startR < str.size(); startR++) { int L = 0; int R = startR; while (R < str.size()) { int p1 = dp[L+1][R]; int p2 = dp[L][R-1]; int p3 = str[L] == str[R] ? 2 + dp[L+1][R-1] : 0; dp[L][R] = max(p1 , max(p2 , p3)); L++; R++; } } return dp[0][str.size()-1]; }
