Участник:PinkHedgehog/CDPS
Материал из DISCOPAL
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]