最近在学习动态规划中遇到了这一类型的题目，这里将这一类型的所有题目总结了一下
1、 最长回文子串
1.1、题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
1.2、题解
问题分析
这个问题是此类问题的基础形式，首先这道题比较麻烦的就是判断一个子串是否是回文子串，因此需要一种能够快速判断原字符串中所有子串是否是回文子串的方法。所以想到了动态规划。
动态规划的最主要的步骤就是要知道状态如何转移。暂且回到这个问题来看，回文（ 其实是具有天然转移特性的，为什么这么说呢？这当然不是空穴来风了。
- 一个回文去掉头和尾之后，剩下的部分依然是一个回文（暂时不考虑边界情况）
大家仔细想想这句话，回文是不是一定满足这个性质O(∩_∩)O。
让我们从回文串的定义开始展开讨论：
- 如果一个字符串的头尾字符不相等，那么这个字符串一定不是一个回文串。
- 如果一个字符串的头尾字符相等，那么我们的问题将会变成考虑==“这个字符串去掉头尾之后，剩余的部分是不是回文”==此时会有两种情况出现：
- 如果剩余部分是回文串的话，那这个字符串是回文串。
- 如果剩余部分不是回文串的话，那这个字符串一定不是回文串。
根据上述讨论可得到：在头尾字符相等的情况下，里面子串的回文性质规定了整个子串的回文性质。所以这就是状态转移，因此可以把状态定义为：原字符串的一个子串是否是回文子串。
第一步：定义状态
设定 dp[i][j] 表示子串s[i..j]是否是回文子串，这里的s[i..j]是一个闭区间，可以取到s[i] 和 s[j]。
第二步：考虑状态转移方程
根据上述分类讨论总结（根据头尾字符是否相等）可得：
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
说明：
- 动态规划实际上是在填一张二维的表格，由于要构成子串，所以这里
i和j的关系是i <= j，因此只要填表格的对角线的上部分即可。 - 还有一个问题就是方程中的
dp[i + 1][j - 1]，因为要构成子串，所以这里就要考虑边界情况了。
边界条件是：i + 1 <= j - 1，这样才能构成子串。即：j - i <= 2或者j - i < 3。
这个结论很明显，当子串s[i .. j]的长度等于2或者等于3的时候，只需判断头尾字符是否相等即可决定这个子串是否是回文子串了。
- 如果
s[i + 1 ... j - 1]只有一个字符的话，那么去掉两头，剩下的部分只有一个字符，那一定是回文子串。 - 如果
s[i + 1 .. j - 1]是空串的话，那么子串s[i .. j]一定是回文子串。
因此，在s[i] == s[j]和j - i < 3都成立的情况下，dp[i][j]为true。否则才考虑转移。
那么转移方程可以写成：dp[i][j] = (s[i] == s[j]) && (j - i < 3 || dp[i + 1][j - 1])。
第三步：考虑初始化
当只有一个字符的时候一定是回文子串，所以对角线都为true，即dp[i][i] = true。但在这里我们可以不需要初始化，因为当只有一个字符的时候一定是回文子串，dp[i][i]完全不会被其他状态值影响。
参考代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
string s, res;
bool dp[maxn][maxn];
int main() {
cin >> s;
int n = s.length(), ans = -1;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) dp[i][j] = true;
if (dp[i][j]) {
if (j - i + 1 > ans) {
ans = j - i + 1;
res = s.substr(i, j + 1);
}
}
}
}
cout << res << endl;
return 0;
}
2、最长回文子序列
2.1、题目
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例1：
输入："bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb"。
示例2：
输入："cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb"。
2.2、题解
问题分析
这是一道典型的区间dp问题。这里需要注意的是分清楚子串和子序列的区别。子串是连续的，子序列是可以不连续的。而这题是子序列，是可以不连续的。
我们先假设S是区间s[i .. j]中的最长回文子序列，s的长度是n，那么s具有以下两种情况：
n == 1，即S的长度为1。n > 1，即S的长度大于1，那么一定满足S[0] == S[n - 1]，即头和尾字符一定相等。
那么现在问题就变得简单多了，既然S是区间s[i .. j]中的最长回文子序列，那么对于S来说，去掉头尾字符后，S[1 .. n - 2]也是回文的，同时也是区间S[i + 1 .. j - 1]的最长回文子序列。所以可以推得：区间S[i .. j]的最长回文子序列的长度为区间S[i + 1 .. j - 1]的最长回文子序列长度 + 2。
第一步：定义状态
设定dp[i][j]表示区间s[i .. j]的最长回文子序列的长度，s[i .. j]是一个闭区间，可以取到s[i] 和 s[j]。
第二步：考虑状态转移方程
根据以上分析，可以推出方程为：
- 若头尾字符相等，那么
dp[i][j] = dp[i + 1][j - 1] + 2。 - 若头尾字符不相等，那么
dp[i][j] = max(dp[i + 1][j]，dp[i][j - 1])。
说明：
- 如果头尾字符相等的话，那区间
[i .. j]的最长回文子序列的长度就是区间[i + 1 .. j - 1]的最长回文子序列长度 +2。 - 如果头尾字符不相等的话，那区间
[i .. j]的最长回文子序列的长度就变成求区间[i + 1 .. j]和区间[i .. j - 1]的最长回文子序列的长度，两者取最大值。
第三步：考虑初始化
和上题求最长回文子串一样，当只有一个字符的时候，一定是最长回文子序列，那么dp[i][i] = 1。
参考代码：
#include<bists/stdc++.h>
using namespace std;
const int maxn = 1005;
string s;
int dp[maxn][maxn];
int main() {
cin >> s;
int n = s.length();
for (int j = 0; j < n; j++) {
dp[j][j] = 1;
for (int i = j - 1; i >= 0; i--) {
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
cout << dp[0][n - 1] << endl;
return 0;
}
评论