给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。
通过从 s 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。
挺难的一道题。
使用dp的话，记录下历史的值，就不需要dfs的cache。
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
# 这道题的核心是从外往内部寻找可能性
# 如果是从内部往外部寻找可能性，就有可能出现重复
# 字符串寻找的时候，从左往右找不到，就从右往左赵
# 本例是从里面往外找不到，就要从外边往里面找
# 步骤如下：
# 对于['a', 'b', 'c' , 'd']中的任意一个x1，
# 寻找最外边的'x1x1'
# 对于['a', 'b', 'c' , 'd']中的任意一个x2，
# 往内部寻找x1x2x2x1、x1x2x1
@cache
def dfs(c, l, r):
if l == r:
if s[l] == c:
return 1
else:
return 0
elif l > r:
return 0
if s[l] == s[r] == c:
num = 2
for c in ['a', 'b', 'c', 'd']:
num += dfs(c, l+1, r-1)
return num
elif s[l] == c and s[r] != c:
return dfs(c, l, r-1)
elif s[r] == c and s[l] != c:
return dfs(c, l+1, r)
else:
return dfs(c, l+1, r-1)
num = 0
for c in ['a', 'b', 'c', 'd']:
num += dfs(c, 0, len(s)-1)
return num % (10**9 + 7)
