解法：区间dp问题（动态规划）

解决思路：

1. 状态表示

dp[ i ][ j ] ：表示字符串在区间 [ i , j ] 中，最长回文子序列的长度

2. 状态转移方程

  • 如果 i > j ，则区间 [ i , j ] 不合法，故 dp[ i ][ j ] = 0 ；
  • 如果 i == j ，则区间 [ i , j ] 表示的是一个字符，一个字符也是回文序列，故 dp[ i ][ j ] = 1；
  • 如果 i < j ，则区间 [ i , j ] 合法，这是有有两种情况
  • 如果 s[ i ] == s[ j ] ，则说明 s[ i ] 和 s [ j ] 可以加入最长回文子序列，则 dp[ i ][ j ] = dp[ i + 1 ] [ j - 1 ] + 2；
  • 如果 s[ i ] != s[ j ] ，则说明 s[ i ] 和 s [ j ] 不能同时选了，可以退而求其次，在[ i , j - 1 ] 区间中去求最长回文子序列，即 dp[ i ] [ j - 1 ]，在[ i + 1 , j ] 区间中去求最长回文子序列，即 dp[ i + 1 ] [ j ]，我们需要求出它们两个之间的最大值，即 dp[ i ][ j ] = max( dp[ i ] [ j - 1 ] , dp[ i + 1 ] [ j ] )；

3. 初始化

其实不用管，因为我们在填表的时候需要的值是当前位置的左边，左下，下变，这三个值，当时因为当 i == j 时，我们会填表为 1，而在dp表的左下半部分是基本用不到的（除了临近i==j的位置，需要用它求max），所以我们填表只需要将全部初始化为0即可。

4. 填表顺序

从下向上，从左向右。因为用到的值是当前位置的左边，左下，下变，这三个值，必须保证这三个位置有值。

5. 结果

整个字符串为 [ 0, s.size() - 1 ] 的区间，所以答案为 dp[ 0 ][ s.size() - 1 ] 。

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

const int N = 1e3 + 10;
int dp[N][N]; // 1.创建dp表+初始化(初始化为0就可以了)
string s;

int main()
{
    cin >> s;
    int n = s.size();

    // 2. 填表
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = i; j < n; j++)
        {
            if(i == j) dp[i][j] = 1;
            else if(i < 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]);
            }
            else dp[i][j] = 0;
        }
    }
    // 3.输出结果
    cout << dp[0][n - 1];
    return 0;
}