大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

动态规划

题目解答方法的文字分析

题目要求在一群牛的编号中找出最长的回文子序列。回文子序列是指从原序列中删除若干个字符（也可以不删除）得到的序列，且该序列正读反读都一样。

思路：使用动态规划来解决此问题。

动态规划状态定义：我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从第 i 个字符到第 j 个字符的最长回文子序列的长度。

动态规划转移方程：

  1. 当 i == j 时，说明只有一个字符，自身就是回文子序列，此时 dp[i][j] = 1。
  2. 当 i < j 时，如果 s[i] == s[j]，说明 s[i] 和 s[j] 可以构成回文子序列的一对字符，所以 dp[i][j] = dp[i + 1][j - 1] + 2。
  3. 当 s[i] != s[j]，说明 s[i] 和 s[j] 不能构成回文子序列的一对字符，此时需要在 s[i] 和 s[j] 中分别去掉一个字符，取 dp[i + 1][j] 和 dp[i][j - 1] 的较大值。

动态规划初始化：dp[i][i] = 1，因为单个字符是回文子序列。

最终答案：最长回文子序列的长度即为 dp[0][n-1]，其中 n 是字符串 s 的长度。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n, 0)); // dp[i][j] 表示从第 i 个字符到第 j 个字符的最长回文子序列的长度
        
        // 单个字符是回文子序列，长度为 1
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }
        
        // 从长度为 2 的子序列开始递推
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i < n - len + 1; ++i) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    // s[i] 和 s[j] 可以构成回文子序列的一对字符，所以 dp[i][j] = dp[i + 1][j - 1] + 2
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    // s[i] 和 s[j] 不能构成回文子序列的一对字符，需要在 s[i] 和 s[j] 中分别去掉一个字符，
                    // 取 dp[i + 1][j] 和 dp[i][j - 1] 的较大值
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[0][n - 1]; // 最长回文子序列的长度即为 dp[0][n-1]
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！