#include <iostream>
#include <string>
#include <vector>
#include <algorithm>  // 用于max函数
using namespace std;

int main() 
{
    string str;
    cin >> str;  // 读取输入字符串

    int n = str.size();  // 获取字符串长度
    vector<vector<int>> dp(n, vector<int>(n, 0));  // 创建二维数组dp，dp[i][j]表示str[i..j]的最长回文子序列长度
    
    // 初始化：单个字符的最长回文子序列长度为1
    for(int i = 0; i < n; i++) 
        dp[i][i] = 1;

    // 按子串长度从小到大遍历，从长度2开始，直到整个字符串
    for(int len = 2; len <= n; len++)
    {
        // 遍历所有可能的起始索引i
        for(int i = 0; i + len <= n; i++)
        {
            int j = i + len - 1;  // 计算对应的结束索引
            
            // 如果当前子串的首尾字符相同
            if(str[i] == str[j]) 
                dp[i][j] = dp[i + 1][j - 1] + 2;  // 长度为中间部分的长度加2
            
            // 如果首尾字符不同
            else 
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);  // 取舍弃首字符或尾字符后的最大值
        }
    }
    
    // 输出整个字符串的最长回文子序列长度
    cout << dp[0][n - 1] << endl;
    return 0;
}

题目分析：最长回文子序列（Longest Palindromic Subsequence）

这道题要求我们找到给定字符串中的最长回文子序列的长度。回文子序列是指从原字符串中删除 0 个或多个字符后，剩余字符按原顺序排列形成的字符串，且该字符串正读和反读都相同。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb"，长度为 4。

解题思路：动态规划

1. 问题分解与状态定义

动态规划的核心是将原问题分解为更小的子问题，并存储子问题的解以避免重复计算。对于这道题，我们定义状态：

  • dp[i][j] 表示字符串从索引 i 到索引 j 的子串中，最长回文子序列的长度。

2. 状态转移方程

对于子串 str[i..j]，我们考虑以下两种情况：

  1. 如果 str[i] == str[j]：两端字符可以同时包含在回文子序列中，因此 dp[i][j] = dp[i+1][j-1] + 2。例如，对于子串 "abba"，由于首尾字符都是 'a'，其最长回文子序列长度为中间子串 "bb" 的长度加 2。
  2. 如果 str[i] != str[j]：两端字符不能同时包含，因此我们需要舍弃一端，取两种情况中的最大值：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。例如，对于子串 "abca"，由于首尾字符不同，我们可以选择包含首字符 'a' 并检查子串 "bc"（即 dp[i][j-1]），或者包含尾字符 'a' 并检查子串 "bc"（即 dp[i+1][j]），取两者中的最大值。

3. 初始化条件

  • 对于单个字符，其最长回文子序列长度为 1，即 dp[i][i] = 1。

4. 遍历顺序

为了确保在计算 dp[i][j] 时，所有依赖的子问题（如 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]）已经被解决，我们按子串长度从小到大遍历：

  1. 先处理长度为 2 的子串，再处理长度为 3 的子串，以此类推，直到处理整个字符串。
  2. 对于每个长度 len，遍历所有可能的起始索引 i，计算对应的结束索引 j = i + len - 1。