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

以下是 Python 代码实现：

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        n = len(s)
        dp = [[-1] * n for _ in range(n)]
        MOD = 10**9 + 7

        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            if i == j:
                return 1
            if dp[i][j] != -1:
                return dp[i][j]
            res = 0
            if s[i] != s[j]:
                res = dfs(i + 1, j) + dfs(i, j - 1) - dfs(i + 1, j - 1)
            else:
                l, r = i + 1, j - 1
                while l <= j and s[l] != s[i]:
                    l += 1
                while r >= i and s[r] != s[i]:
                    r -= 1
                if l > r:
                    res = dfs(i + 1, j - 1) * 2 + 2
                elif 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
            return dp[i][j]

        return dfs(0, n - 1)

时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。由于需要使用递归，因此实际运行时间可能比较慢。