Участник:PinkHedgehog/CDPS

Ссылки сюда (1) →

https://leetcode.com/problems/count-different-palindromic-subsequences

class Solution:
    def countPalindromicSubsequences(self, S: str) -> int:
        l = len(S)
        dp = [ [0] * l for _ in range(l)]
        for i in range(l):
            dp[i][i] = 1
 
        for dist in range(1, l):
            for i in range(0, l-dist):
                j = i + dist
                if S[i] == S[j]:
                    low = i + 1
                    high = j - 1
 
                    while low <= high and S[low] != S[j]:
                        low += 1
                    while low <= high and S[high] != S[j]:
                        high -= 1
 
                    if low > high:
                        dp[i][j] = dp[i+1][j-1]*2 + 2
                    elif low == high:
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1]
                else:
                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]
                if dp[i][j] < 0:
                    dp[i][j] += 1000000007
                else:
                    dp[i][j] %= 1000000007
        return dp[0][l - 1]