题目定位
这题适合做 DP，因为 s[i..j] 是否回文取决于更小的内部子串以及当前两端字符是否相等。
关键观察
一个子串是回文，当且仅当两端字符相等，且内部子串也回文；长度较短时直接由 base case 处理。
目标复杂度
O(n^2) / O(n^2)
这题的解法思路怎么拆
1
这题适合做 DP，因为 s[i..j] 是否回文取决于更小的内部子串以及当前两端字符是否相等。
2
一个子串是回文，当且仅当两端字符相等，且内部子串也回文；长度较短时直接由 base case 处理。
3
先用自然语言命名状态。
4
列出哪些决策会转移到这个状态。
参考实现
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
常见坑点
warning
遍历顺序写错，导致 dp[i+1][j-1] 还没算出来。
warning
忘了长度 1 和 2 的子串需要特殊初始化。
高频追问
除了 DP，还有中心扩展写法吗？
如果只关心长度，能否进一步降空间？
继续刷相关题
先把 动态规划 这个模式刷成体系，再去做更难变体。