最长回文子序列动态规划c++

最长回文子序列（Longest Palindromic Subsequence，LPS）问题是指在一个给定的字符串中找到一个最长的回文子序列。回文子序列是指一个序列本身不是回文串，但它是一个回文串的子序列。

在C++中，我们可以使用动态规划（Dynamic Programming，DP）的方法来解决这个问题。动态规划的主要思想是将一个大问题分解成小问题，然后从小问题出发，逐渐求得大问题的解。

以下是一个使用动态规划解决最长回文子序列问题的C++示例代码：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 函数用于计算字符串str的最长回文子序列的长度
int longestPalindromeSubseq(string str) {
    int n = str.size();
    // 创建一个二维数组dp，用于存储子问题的解，初始化所有值为0
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // 单个字符的最长回文子序列长度为1，所以对角线上的元素设置为1
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    // 如果两个字符相同，那么它俩组成的子序列长度为2
    for (int cl = 2; cl <= n; cl++) {
        for (int i = 0; i < n - cl + 1; i++) {
            int j = i + cl - 1;
            if (str[i] == str[j] && cl == 2) {
                dp[i][j] = 2;
            } else if (str[i] == str[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        }
    }
    
    // 返回整个字符串的最长回文子序列长度
    return dp[0][n - 1];
}

int main() {
    string str;
    cout << "请输入一个字符串：" << endl;
    cin >> str;
    cout << "最长回文子序列的长度为：" << longestPalindromeSubseq(str) << endl;
    return 0;
}

在这段代码中，`dp[i][j]`表示从字符串的第`i`个字符到第`j`个字符组成的子串的最长回文子序列的长度。通过初始化对角线以及递推式逐步填充这个二维数组，最终可以得到整个字符串的最长回文子序列长度。