题目描述 什么是回文呢？那就是对称的字符串。For example，abcdcba是回文的，abccba也是回文的。那么在一个字符串abccbaabcc，你能找到很多回文的子序列，例如abccba，ccbaabcc，那么最长的就是ccbaabcc，长度为8。 输入要求 输入一行字符串，由小写英文字母表示，字符长度小于1000。 输出要求 输出最长回文子序列的长度。 输入样例 abccbaabcc 输出样例 8

这是一个经典的动态规划问题。我的回答如下：

我们可以用一个二维数组 `dp` 来表示字符串 `s` 在区间 `[i,j]` 中的最长回文子序列长度。其中 `dp[i][j]` 表示字符串 `s` 在区间 `[i,j]` 中的最长回文子序列长度。显然，当 `i==j` 时，`dp[i][j]` 的值为1，因为一个字符本身就是一个回文。当 `s[i]==s[j]` 时，显然字符串 `s` 在区间 `[i,j]` 中的最长回文子序列长度是 `dp[i+1][j-1] + 2`，因为首尾字符相等，所以最长回文子序列的长度就是去掉首尾字符后的最长回文子序列长度加上2。当 `s[i]!=s[j]` 时，最长回文子序列要么是在区间 `[i,j-1]` 中，要么是在区间 `[i+1,j]` 中，取两者中的最大值即可。

最后，所求的最长回文子序列长度就是 `dp[0][n-1]`，其中 `n` 是字符串 `s` 的长度。

下面是一份C++的代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;

int dp[N][N];

int main() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            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;
}

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。