定义
子问题的转移形式是从小区间到大区间，而非前缀或后缀的转移
算法
记忆化搜索
python
from functools import cache
fair = lambda x, y: abs(ord(x) - ord(y)) == 1 or abs(ord(x) - ord(y)) == 25
@cache
def dfs(i, j):
# s == ''
if i > j:
return True
if fair(i, j) and dfs(i + 1, j - 1):
return True
# 步长为2
for k in range(i + 1, j - 1, 2):
if dfs(i, k) and dfs(k + 1, j):
return True
return False递推
python
n = len(s)
fair = lambda x, y: abs(ord(x) - ord(y)) == 1 or abs(ord(x) - ord(y)) == 25
f = [[False] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
f[i + 1][i] = True
for j in range(i + 1, n, 2):
if fair(s[i], s[j]) and f[i + 1][j - 1]:
f[i][j] = True
continue
for k in range(i + 1, j - 1, 2):
if f[i][k] and f[k + 1][j]:
f[i][j] = True
breakpython
n = len(s)
fair = lambda x, y: abs(ord(x) - ord(y)) == 1 or abs(ord(x) - ord(y)) == 25
f = [[False] * n for _ in range(n)]
for length in range(2, n + 1, 2):
for i in range(n - l + 1):
f[i + 1][i] = True
j = i + length - 1
if fair(s[i], s[j]) and f[i + 1][j - 1]:
f[i][j] = True
continue
for k in range(i + 1, j - 1, 2):
if f[i][k] and f[k + 1][j]:
f[i][j] = True
break