c++求回文子序列个数

回文子序列的个数可以通过动态规划来计算。以下是一个C++示例代码，用于计算给定字符串中回文子序列的个数：

#include <iostream>
#include <cstring>

int countPalindromicSubsequences(const std::string& str) {
    int n = str.length();
    
    // dp[i][j]表示从i到j的子串中回文子序列的个数
    int dp[n][n];
    memset(dp, 0, sizeof(dp));

    // 每个单字符都是长度为1的回文子序列
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // 遍历长度为2到n的子串
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            // 如果首尾字符相同，可以在原有的回文子序列基础上新增2个，再加上新的两个单字符
            if (str[i] == str[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                // 如果首尾字符不同，分别计算去掉首字符和去掉尾字符后的子串中的回文子序列个数
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
            }

            // 处理重复计算的情况
            if (str[i] == str[j]) {
                int k = i + 1;
                int m = j - 1;
                while (k <= m && str[i] == str[k]) {
                    k++;
                }
                while (k <= m && str[j] == str[m]) {
                    m--;
                }
                if (k <= m) {
                    dp[i][j] += 1; // 加上重复的回文子序列个数
                }
            }
        }
    }

    return dp[0][n - 1];
}

int main() {
    std::string input;
    std::cout << "请输入字符串: ";
    std::cin >> input;

    int result = countPalindromicSubsequences(input);

    std::cout << "回文子序列的个数是: " << result << std::endl;

    return 0;
}

这段代码使用动态规划来计算给定字符串中回文子序列的个数。在 countPalindromicSubsequences 函数中，dp[i][j] 表示从索引 i 到 j 的子串中回文子序列的个数。