题解 | #编号子回文II#

考察的知识点：动态规划；

解答方法分析：

1. 定义一个二维数组dp，其中dp[i][j]表示从字符串s的第i个字符到第j个字符之间的最长回文子序列的长度。
2. 对于长度为1的子序列，dp[i][i]的值都为1。
3. 根据子序列的长度逐步增加，对于长度为len的子序列，遍历所有起始位置i，计算dp[i][i+len-1]的值。
4. 如果s[i]等于s[i+len-1]，则dp[i][i+len-1]的值等于dp[i+1][i+len-2]的值上2，即字符串s的第i+1个字符到第i+len-2个字符之间的最长回文子序列的长度加上2如果s[i]不等于s[i+len-1]，则dp[i][i+len-1]的值等于dp[i+1][i+len-1]和dp[i][i+len-2]中的较大值。
5. 返回dp[0][n-1]。

所用编程语言：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));
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int len = 2; len <= n; len++) {
            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];
    }
};