题解 | #最长回文子序列# ✅✅✅经典二维DP秒杀

关键词：动态规划

核心思想：使用动态规划来计算最长回文子序列的长度。通过构建一个二维数组 dp，其中 dp[i][j] 表示字符串 str 从索引 i 到 j 的最长回文子序列的长度。

解题步骤：

1. 初始化一个二维数组 dp，其大小为 l x l（l 为字符串长度），所有元素初始化为0。
2. 对于每个单字符回文，设置 dp[i][i] = 1。
3. 从后往前遍历字符串，填充 dp 数组：
1. 如果 str[i] == str[j]，则 dp[i][j] = dp[i + 1][j - 1] + 2
2. 否则dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
4. 最后，输出 dp[0][l - 1]，即整个字符串的最长回文子序列长度。

时间和空间复杂度：时间复杂度：O(n²)，因为有两重循环遍历字符串。空间复杂度：O(n²)，用于存储DP表。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int l = str.length();
    vector< vector<int>> dp(l, vector<int>(l, 0));

    // 从后往前处理字符串
    for (int i = l - 1; i >= 0; i--) {
        dp[i][i] = 1; // 单字符是长度为1的回文串
        for (int j = i + 1; j < l; j++)
            if (str[i] == str[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][l - 1] << endl;
    return 0;
}