动态规划-最长回文子序列
题目描述
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bcbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
解题思路
在此前我们已经介绍了一些关于子序列的题目，其中的动态规划思路基本都是 以dp[i] 表示以i为结尾的子串中其中最长的回文子序列的长度。但是在本题中我们不用这种方法，因为
-
状态定义不准确：
如果dp[i]表示以i为结尾的子串中最长的回文子序列的长度，那么这个定义忽略了子序列的起始位置。在LPS问题中，我们需要考虑的是从某个位置i开始到某个位置j结束的子串中的最长回文子序列，而不仅仅是结束位置。因此，一个更合适的状态定义是dp[i][j]，它同时考虑了子串的起始和结束位置。 -
状态转移困难：
如果只用dp[i]来表示，那么很难从前面的状态推导出当前状态。因为最长回文子序列可能并不总是以i结尾，且它的起始位置可能远远早于i。在动态规划中，状态转移方程是非常重要的，它决定了如何从已知的子问题解推导出当前问题的解。如果状态定义不准确，那么状态转移方程也会变得复杂或不可行。 -
无法覆盖所有情况：
使用dp[i]只会考虑以i结尾的子序列，而忽略了可能包含i但不以i结尾的回文子序列。在LPS问题中，我们需要找到的是整个字符串中的最长回文子序列，而不是仅仅以某个字符结尾的最长子序列。 -
无法有效利用回文性质：
回文子序列的一个重要性质是对称性。当我们在字符串的两端找到相同的字符时，我们可以利用这一点来减少需要检查的子问题数量。然而，如果仅使用dp[i]，这种对称性就很难被有效利用，因为我们没有关于子序列起始位置的信息。
所以我们需要用其他方法。通常采用 dp[i][j] 来表示从位置 i 到位置 j 的子串中的最长回文子序列的长度。这种定义方式既考虑了子序列的起始位置，也考虑了结束位置，从而能够更准确地描述问题，并使得状态转移方程变得简单且直观。
动态规划思路
-
定义状态：
设dp[i][j]表示字符串s中从索引i到索引j（包含i和j）的子串的最长回文子序列的长度。 -
初始化：
当i == j时，dp[i][j] = 1，因为单个字符本身就是回文。 -
状态转移方程：
- 首先，对于回文串在其首尾加上相同的两个字符，它仍然是一个回文串。
- 如果
s[i] == s[j]，那么dp[i][j] = dp[i+1][j-1] + 2，因为两端的字符相同，可以加入到回文子序列中，并且内部的回文子序列长度增加了2。 - 如果
s[i] != s[j]，那么dp[i][j] = max(dp[i+1][j], dp[i][j-1])，即最长回文子序列要么不包含s[i]，要么不包含s[j]，取两种情况下的最大值。
- 首先，对于回文串在其首尾加上相同的两个字符，它仍然是一个回文串。
-
结果：
最终答案存储在dp[0][n-1]中，其中n是字符串s的长度。
需要注意的是填表顺序不能按照二维数组从左到右，从上到下的顺序，而是与此前的回文子串题目中相同，按照子串的长度从1到n的顺序填表。
代码示例
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
// 初始化对角线
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
}
// 填充dp表
for (int len = 2; len <= n; ++len) { // 子串长度从2开始
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
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]);
}
}
}
return dp[0][n - 1];
}
};