最长回文子序列

1、题目描述

下面是题目的链接： 516. 最长回文子序列 - 力扣（LeetCode）

对应的题目描述如下：

2、题目解答 + 代码

方法一：动态规划

看到此题，初步的想法就是使用双指针，一个从前面扫描，一个从后面扫描，但是这里是可以删除该字符串中的某一个元素的，因此要是使用双指针的话就比较的麻烦，因此不考虑这一种方式。

我们想一下，啥叫回文，是不是从前读和从后读都是一样的，既然双指针不行，那是不是我可以将所给的字符串进行翻转然后在进行判断，要是某一个回文子序列是所给字符串s的最长回文子序列，那么一定也是反转后的字符串r的最长回文子序列。这样的话，我们就只需要寻找这两个字符串的最长公共子序列即可。

此时dp定义如下：

• dp[i][j] 表示字符串 a 的前 i 个字符与字符串 b 的前 j 个字符的最长公共子序列的长度。
• 这里 a 是原始字符串 s，b 是 s 的反转字符串。

状态转移方程为：

• 如果字符相等 (a[i-1] == b[j-1]): 表示在这两个字符上形成了一个公共子序列，因此 dp[i][j] 应该是 dp[i-1][j-1] 加 1。
• 如果字符不相等 (a[i-1] != b[j-1]): dp[i][j] 是去掉当前字符后的最大公共子序列的长度，即 Math.max(dp[i-1][j], dp[i][j-1])。

依据上面的思路，可以写出下列代码：

class Solution
{
public:
    int longestPalindromeSubseq(string s)
    {
        int n = s.length();
        string r(s.rbegin(), s.rend()); // 反转s字符串
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));// 定义状态转移变量
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (s[i] == r[j])
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                else
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
        return dp[n][n];
    }
};

$$\begin{gathered} 时间复杂度：O(n^2) \\ 空间复杂度：O(n^2) \end{gathered}$$

方法二：依旧是动态规划

方法一的话引入了一个新的字符串，这会导致空间复杂度比较的高，因此下面就是希望就对该字符串进行处理就可以

考虑如此建立状态方程：

假设我已知了字符串中子串s[i:j-1]中的最长回文子序列长度，现在我要在这个子串后添加一个字符s[j]，求子串**s[i:j]的最长回文子序列。由于回文子序列需要两端的元素一样，因此我们需要判断添加的末尾字符s[j]与第一个字符s[i]**是否相等。

如果s[i] == s[j]，那么回文子串的长度就等于去掉首尾这两个字符后，剩余子串的最长回文子序列长度 +2 ，即
$$dp[i][j]=dp[i+1][j-1]+2$$
如果s[i] ！= s[j]，那么回文子串的长度就等于去掉首字符后，剩余子串的最长回文子序列长度 与 去掉尾字符后，剩余子串的最长回文子序列长度二者中较大的那一个 ，即
$$dp[i,j]=max(dp[i+1][j],dp[i][j-1])$$
最后我们考虑一下边界情况：

• （1）当i==j，对应子串仅有一个字符，此时最长回文串长度一定为1，即图中的主对角线。
• （2）当i<j，此时末尾字符在首字符之前，不可能发生，应为0，即主对角线下方元素为0。

基于上述的分析思路，我们可以得出下面的代码：

class Solution
{
public:
    int longestPalindromeSubseq(string s)
    {
        int len = s.length();
        if (len < 2) // 这行代码是必须要的，不然下面的代码对于单个字符的字符串是无法进行判断的
            return len;
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for (int start = len - 2; start >= 0; start--) // 从下至上
        {
            dp[start][start] = 1;                       // 对角线元素为1，即单个字符构成回文子序列
            for (int end = start + 1; end < len; end++) // 从左至右
                dp[start][end] = s[start] == s[end] ? dp[start + 1][end - 1] + 2 : max(dp[start + 1][end], dp[start][end - 1]);
        // { 上面长代码可以翻译成下面的代码的形式
        //     if (s[start] == s[end])
        //         dp[start][end] = dp[start + 1][end - 1] + 2;
        //     else
        //         dp[start][end] = max((dp[start + 1][end], dp[start][end - 1]));
        // }
        }
        return dp[0][len - 1];
    }
};

$$\begin{gathered} 时间复杂度:O(n^2)遍历半个二维矩阵，每个位置O(1)的复杂度，总复杂度O(n^2) \\ 空间复杂度:O(n^2)需要开辟二维矩阵dp，占用空间O(n^2) \end{gathered}$$

也是可以从前至后进行遍历：

class Solution
{
public:
    int longestPalindromeSubseq(string s)
    {
        int len = s.length();
        if (len < 2) 
            return len;
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for (int i = 1; i < len; i++)
        {
            dp[i][i] = 1;
            for (int j = i - 1; j >= 0; j--)
                dp[j][i] = s[i] == s[j] ? dp[j + 1][i - 1] + 2 : max(dp[j + 1][i], dp[j][i - 1]);
        }
        return dp[0][len - 1];
    }
};

对于方法二的进一步优化

发现在进行状态转移时，仅需要用到下一行的数据，无需保留全部二维dp矩阵，因此采用滚动数组优化空间复杂度

详细代码如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        if (len < 2) // 对于长度小于2的字符串，最长回文子序列的长度就是字符串本身的长度
            return len;
        // 使用一个一维数组 dp 来代替二维数组，减少空间复杂度
        vector<int> dp(len, 0);
        // 从最后一个字符向前遍历，即从下至上
        for (int start = len - 2; start >= 0; start--) {
            dp[start] = 1; // 单个字符本身就是回文子序列
            int dpslel = 0; // 用于保存上一轮循环中 dp[start + 1] 的值
            // 遍历从 start + 1 到 len - 1 的所有位置
            for (int end = start + 1; end < len; end++) {
                int temp = dp[end]; // 保存当前 dp[end] 的值
                // 如果 start 和 end 处的字符相同，则回文子序列长度增加2
                // 否则，取 dp[end] 和 dp[end - 1] 中的最大值
                dp[end] = s[start] == s[end] ? dpslel + 2 : max(dp[end], dp[end - 1]);
                // 更新 dpslel 的值，用于下一次循环
                dpslel = temp;
            }
    // 这里就是每次要是从一个start位置进行遍历的时候，就将该位置的dp值置成1.dp[end]表示的是从start到end-1的最长回文子序列
        }
        // 最终结果存储在 dp[len - 1] 中
        return dp[len - 1];
    }
};

滚动数组思想体现

1. 减少空间复杂度:
   • 原始的动态规划解法可能会使用一个二维数组 dp 来存储中间结果。这里通过只保留最近两行的数据，从而将空间复杂度降低到了 O(n)，其中 n 是字符串的长度。
2. 使用一维数组:
   • 代码中使用了一维数组 dp 来存储中间结果。这是因为对于当前的 start 和 end，我们只需要知道前一个 start 和 end 的状态。
3. 更新策略:
   • 代码中的 dp[end] 在每次循环中都会被更新。为了保留前一轮循环的结果，使用了临时变量 temp 和 dpslel 来存储前一轮循环中 dp[end] 的值。这样，每次更新 dp[end] 时都可以正确地参考前一轮的结果。
4. 迭代方向:
   • 代码从后往前迭代（从 len - 2 到 0），这是因为每次更新 dp[end] 都需要依赖于之前已经计算过的值。

通过这种方式，代码有效地利用了一维数组来存储必要的信息，并通过迭代更新策略保证了算法的正确性和效率。这种方法称为滚动数组技术，因为它模拟了二维数组的行为，但仅使用了一维数组，从而节省了空间。