1.题目基本信息
1.1.题目描述
给你一个字符串 s ，返回 s 中不同的非空回文子序列个数 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
字符串的子序列可以经由字符串删除 0 个或多个字符获得。
如果一个序列与它反转后的序列一致，那么它是回文序列。
如果存在某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。
1.2.题目地址
https://leetcode.cn/problems/count-different-palindromic-subsequences/description/
2.解题方法
2.1.解题思路
动态规划
2.2.解题步骤
方法1：动态规划（三维）
-
第一步，状态定义。dp[x][i][j]为s[i,..,j]子串中以字符x为首尾的不同回文子序列的个数
-
第二步，状态初始化。如果s[i]==x，dp[x][i][i]=1；如果s[i]!=x，dp[x][i][i]=0；如果i>j，dp[x][i][j]=0。
-
第三步，状态转移。如果s[i]==s[j]==x，那么dp[x][i][j]=2+sum(dp[x_k][i+1][j-1] for x_k in ['a','b','c','d'])；如果s[i]==x!=s[j]，dp[x][i][j]=dp[x][i][j-1]；如果s[i]!=x==s[j]，dp[x][i][j]=dp[x][i+1][j]；如果s[i]!=x且s[j]!=x，dp[x][i][j]=dp[x][i+1][j-1]
-
第四步，题解即为sum(dp[x][0][n-1] for x in ['a','b','c','d'])
方法2：动态规划（二维）
-
第一步，状态定义。dp[i][j]表示s[i,...,j]子串中不同回文子序列的个数
-
第二步，状态初始化。dp[i][i]=1；如果i>j，dp[i][j]=0
-
第三步，状态转移。定义「边缘字符」为回文子序列两侧相同的字符；易知dp[i][j]为[i,j]区间中以四种字符分别作为「边缘字符」共同组成的不同回文子序列数构成。针对枚举到字符k作为「边缘字符」时，如果[i,j]区间中没有字符k，则贡献为0；如果[i,j]区间存在大于等于1个字符k，记[l,r]中第一个出现的字符k的下标为low，最后一个出现的字符k的下标为high，如果low==high，则贡献为1；如果low+1==high，则有k和kk两种情形，贡献为2；对于其他情况，贡献为dp[low+1][high-1]+2。同时在遍历的过程使用L[4]和R[4]分别维护遍历的区间中最靠左和最靠右的每个字符的位置
-
第四步，题解即为dp[0][n-1]
3.解题代码
python3代码-动态规划（三维）
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
# 方法1：动态规划（三维）
n = len(s)
mod = 10 ** 9 + 7
# 第一步，状态定义。dp[x][i][j]为s[i,..,j]子串中以字符x为首尾的不同回文子序列的个数
dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(4)]
# 第二步，状态初始化。如果s[i]==x，dp[x][i][i]=1；如果s[i]!=x，dp[x][i][i]=0；如果i>j，dp[x][i][j]=0。
for k in range(4):
ch = chr(k + ord('a'))
for i in range(n):
if s[i] == ch:
dp[k][i][i] = 1
# 第三步，状态转移。如果s[i]==s[j]==x，那么dp[x][i][j]=2+sum(dp[x_k][i+1][j-1] for x_k in ['a','b','c','d'])；如果s[i]==x!=s[j]，dp[x][i][j]=dp[x][i][j-1]；如果s[i]!=x==s[j]，dp[x][i][j]=dp[x][i+1][j]；如果s[i]!=x且s[j]!=x，dp[x][i][j]=dp[x][i+1][j-1]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
for k in range(4):
ch = chr(ord('a') + k)
if s[i] == s[j] == ch:
dp[k][i][j] = (2 + sum(dp[x][i + 1][j - 1] for x in range(4))) % mod
elif s[i] == ch and s[j] != ch:
dp[k][i][j] = dp[k][i][j - 1]
elif s[i] != ch and s[j] == ch:
dp[k][i][j] = dp[k][i + 1][j]
else:
dp[k][i][j] = dp[k][i + 1][j - 1]
# 第四步，题解即为sum(dp[x][0][n-1] for x in ['a','b','c','d'])
return sum(dp[k][0][n - 1] for k in range(4)) % modpython3代码-动态规划（二维）
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
# 方法2：动态规划（二维）
n = len(s)
mod = 10 ** 9 + 7
# 第一步，状态定义。dp[i][j]表示s[i,...,j]子串中不同回文子序列的个数
dp = [[0] * n for _ in range(n)]
# 第二步，状态初始化。dp[i][i]=1；如果i>j，dp[i][j]=0
for i in range(n):
dp[i][i] = 1
# 第三步，状态转移。定义「边缘字符」为回文子序列两侧相同的字符；易知dp[i][j]为[i,j]区间中以四种字符分别作为「边缘字符」共同组成的不同回文子序列数构成。针对枚举到字符k作为「边缘字符」时，如果[i,j]区间中没有字符k，则贡献为0；如果[i,j]区间存在大于等于1个字符k，记[l,r]中第一个出现的字符k的下标为low，最后一个出现的字符k的下标为high，如果low==high，则贡献为1；如果low+1==high，则有k和kk两种情形，贡献为2；对于其他情况，贡献为dp[low+1][high-1]+2。同时在遍历的过程使用L[4]和R[4]分别维护遍历的区间中最靠左和最靠右的每个字符的位置
L = [-1] * 4
for i in range(n - 1, -1, -1):
L[ord(s[i]) - ord('a')] = i
R = [-1] * 4
R[ord(s[i]) - ord('a')] = i
for j in range(i + 1, n):
R[ord(s[j]) - ord('a')] = j
for k in range(4):
low, high = L[k], R[k]
if high == -1:
# > [i,j]区间不存在字符k
continue
else:
if low == high:
dp[i][j] += 1
elif low + 1 == high:
dp[i][j] += 2
else:
dp[i][j] += (dp[low + 1][high - 1] + 2) % mod
# 第四步，题解即为dp[0][n-1]
return dp[0][n - 1] % mod4.执行结果
