记忆化搜索
python
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- 本文链接：https://io.helltractor.top/posts/algorithm/interval-dp
- 版权声明：本博客所有文章除特别声明外，均默认采用 CC BY-NC-SA 许可协议。
