C++力扣730统计不同回文子序列 程序代码

以下是 C++ 代码实现：

class Solution {
public:
    int countPalindromicSubsequences(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        const int MOD = 1e9 + 7;

        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i > j) return 0;
            if (i == j) return 1;
            if (dp[i][j] != -1) return dp[i][j];

            int res = 0;
            if (s[i] != s[j]) {
                res = dfs(i + 1, j) + dfs(i, j - 1) - dfs(i + 1, j - 1);
            } else {
                int l = i + 1, r = j - 1;
                while (l <= j && s[l] != s[i]) l++;
                while (r >= i && s[r] != s[i]) r--;
                if (l > r) {
                    res = dfs(i + 1, j - 1) * 2 + 2;
                } else if (l == r) {
                    res = dfs(i + 1, j - 1) * 2 + 1;
                } else {
                    res = dfs(i + 1, j - 1) * 2 - dfs(l + 1, r - 1);
                }
            }
            dp[i][j] = (res + MOD) % MOD;
            return dp[i][j];
        };

        return dfs(0, n - 1);
    }
};

时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。需要注意的是，为了避免数组下标越界，需要将 dp 数组初始化为 -1。