一、问题背景：最长回文子串 & 为何想到 DP
题目（LeetCode 5 Longest Palindromic Substring）：给一个字符串 s，返回其中最长的回文子串。geeksforgeeks+1
关键特征：
只考虑连续子串，不是子序列。
回文的定义是「从左往右、从右往左读都一样」。
约束：长度最多 1000，用 O(n2)O(n^2)O(n2) 时间、O(n2)O(n^2)O(n2) 或 O(1)O(1)O(1) 空间都可以接受。leetcode+1
这类题有一个非常自然的想法：
既然答案是「某个子串」，那就考虑所有区间 [i,j][i, j][i,j]，看它是不是回文，并在过程中维护最长长度。这恰好是**区间 DP（interval DP）**的典型场景。geeksforgeeks+2
二、区间 DP 的基本套路
区间 DP 的核心模式很固定：
在一个一维序列上，用 dp[i][j]dp[i][j]dp[i][j] 来描述「区间 [i,j][i, j][i,j] 的某种状态/最优值」，再由小区间推导大区间。algo+1
- 什么时候用区间 DP？
这几个特征是「提示你可以考虑 interval DP」的信号：olox+2
输入是一个数组或字符串；
问题跟「子区间」的性质/代价有关（例如是否回文、最小费用、最大收益等）；
大区间的答案能由一个或多个更小子区间的答案组合出来。
典型题目：
最长回文子串、最长回文子序列；algo+1
石子合并、矩阵连乘；geeksforgeeks+1
戳气球（Burst Balloons）、切木棍、区间博弈等。algo+2
- 通用状态和遍历模板
状态定义（通用）：
dp[i][j]dp[i][j]dp[i][j]：对区间 [i,j][i, j][i,j] 的某种「最优值」或「是否成立的属性」。具体含义由题目决定。oi-wiki+2
遍历顺序（核心模板）：
外层遍历子区间长度 len 从 1 到 n；
内层枚举起点 i，从 0 到 n - len，终点 j = i + len - 1。algo+2
这样能保证：
当你处理长度为 len 的区间 [i,j][i, j][i,j] 时，所有长度小于 len 的区间都已经处理完，因为它们在更小的 len 时已经被遍历过。
这就是你常看到的那种循环结构：
for len in 1..n: for i in 0..(n-len): j = i + len - 1 // 这里计算 dp[i][j]「遍历 1~n-len」干的就是这件事：穷举所有区间，并且保证「短区间先于长区间」。olox+1
三、最长回文子串的 DP 解法
针对最长回文子串，先给出一个清晰的 DP 思路，再把它放回区间 DP 框架里。logicmojo+2
- 状态定义：dp[i][j] 是不是回文
这里的定义非常重要：
dp[i][j]dp[i][j]dp[i][j] 是一个布尔值，表示子串 s[i…j]s[i…j]s[i…j]（闭区间）是否是回文串。geeksforgeeks+1
注意：它表示的是「是否为回文」，不是回文长度。长度我们直接用 j−i+1j - i + 1j−i+1 来算。
这么定义的好处：
判断「更长区间」是不是回文，可以直接依赖「内部更短区间」是不是回文，这符合 DP 的递推思想。algo+1
- 基本情况：len = 1 和 len = 2
两种最短区间要单独处理好，否则后面的转移会出问题。algo+1
1）len = 1：
任意单字符都是回文。
所以：对所有 i，设 dp[i][i]=truedp[i][i] = truedp[i][i]=true。
同时可以初始化答案：maxLen = 1, start = 0。geeksforgeeks+1
2）len = 2：
子串 s[i…i+1]s[i…i+1]s[i…i+1] 是不是回文，完全取决于 s[i]==s[i+1]s[i] == s[i+1]s[i]==s[i+1]。
如果相等，设 dp[i][i+1]=truedp[i][i+1] = truedp[i][i+1]=true，并更新答案：maxLen = 2, start = i。geeksforgeeks+1
为什么 len = 2 需要特别处理？
因为通用转移式会访问 dp[i+1][j−1]=dp[i+1][i]dp[i+1][j-1] = dp[i+1][i]dp[i+1][j−1]=dp[i+1][i]，这是一个「空区间」，你不可能再往下依赖它，这种情况要么当作天然为真，要么直接单独判断 len=2。algo+1
- 一般情况：len ≥ 3 的转移方程
对于长度 ≥ 3 的子串 s[i…j]s[i…j]s[i…j]，回文的条件是：
首尾字符相等：s[i]==s[j]s[i] == s[j]s[i]==s[j]；
内部子串 s[i+1…j−1]s[i+1…j-1]s[i+1…j−1] 自己就是回文：dp[i+1][j−1]==truedp[i+1][j-1] == truedp[i+1][j−1]==true。logicmojo+2
因此转移式：
dp[i][j]=(s[i]==s[j])∧dp[i+1][j−1]dp[i][j] = (s[i] == s[j]) \land dp[i+1][j-1]dp[i][j]=(s[i]==s[j])∧dp[i+1][j−1]
如果 dp[i][j]dp[i][j]dp[i][j] 为真，再用 j−i+1j - i + 1j−i+1 去更新当前记录的最长长度 maxLen 和起点 start。algo+1
- 遍历顺序：按 len 从小到大
完整的填表过程可以概括为：
1）预处理 len = 1：所有 dp[i][i]=truedp[i][i] = truedp[i][i]=true。
2）预处理 len = 2：检查每个相邻 pair，若相等则设回文。
3）对 len 从 3 到 n：
对每个 i，算 j = i + len - 1，如果 s[i]==s[j]s[i] == s[j]s[i]==s[j] 且 dp[i+1][j−1]dp[i+1][j-1]dp[i+1][j−1] 为真，就标记 dp[i][j]dp[i][j]dp[i][j] 是回文并更新答案。geeksforgeeks+1
这里「按子串长度递增」是最通用、最直观的 interval DP 模板：
对于 len ≥ 3，内部子串长度是 len-2；
len-2 在你之前的循环里已经处理过，说明 dp[i+1][j−1]dp[i+1][j-1]dp[i+1][j−1] 一定是「已知结果」。oi-wiki+1
- 和「中心扩展」的对比
这个题最常见的最优解其实是「中心扩展」：interviewbit+1
枚举每个下标 i 作为「奇数回文中心」，往两边扩。
枚举每个 pair (i, i+1) 作为「偶数回文中心」，往两边扩。
复杂度也是 O(n2)O(n^2)O(n2)，空间 O(1)O(1)O(1)，面试里一般更推荐写这个。
但从「学习 DP 模板」的角度，二维 DP 版本更有代表性，因为它直接是一个区间 DP 的实例。logicmojo+2
四、区间 DP 的两种转移模式
上面这个回文子串，只用到了「从两端往里缩」这一种模式，其实区间 DP 常见两类转移结构。algo+2
- 模式 A：缩短区间（只看区间两端）
特点：
每一步只用到「去掉一端」或者「两端收缩」得到的更小区间。
典型形式：
dp[i][j]dp[i][j]dp[i][j] 依赖于 dp[i+1][j]dp[i+1][j]dp[i+1][j]、dp[i][j−1]dp[i][j-1]dp[i][j−1] 或 dp[i+1][j−1]dp[i+1][j-1]dp[i+1][j−1]。
例子：
最长回文子串（是否回文）用 dp[i+1][j−1]dp[i+1][j-1]dp[i+1][j−1]。geeksforgeeks+1
区间博弈（两端取数）用 dp[i+1][j]dp[i+1][j]dp[i+1][j]、dp[i][j−1]dp[i][j-1]dp[i][j−1]。algo
这种模式不需要「枚举中间切分点 k」，因此单次转移是 O(1)，整体时间 O(n2)O(n^2)O(n2)。
- 模式 B：中间切一刀（枚举 k）
特点：
大区间 [i,j][i, j][i,j] 的答案，来源于把它切分成两个子区间，再把两边的最优解 + 一次额外代价 合并起来。geeksforgeeks+3
通用结构：
dp[i][j]=min/maxi≤k<j{combine(dp[i][k],dp[k+1][j])+额外代价}dp[i][j] = \min/\max_{i \le k < j} { \text{combine}(dp[i][k], dp[k+1][j]) + \text{额外代价} }dp[i][j]=min/i≤k<jmax{combine(dp[i][k],dp[k+1][j])+额外代价}
典型例子：
矩阵连乘：最后一步把 [i,j][i, j][i,j] 划成 [i,k][i, k][i,k] 和 [k+1,j][k+1, j][k+1,j]，cost = 左 cost + 右 cost + 这两块矩阵相乘的 cost。umd+1
合并石子：[i,j][i, j][i,j] 最后一次合并，左是 [i,k][i, k][i,k]，右是 [k+1,j][k+1, j][k+1,j]，额外代价是区间和 sum(i…j)。topic.alibabacloud+1
Burst Balloons：假设 k 是区间 (i, j) 里最后一个被戳的气球，得分 = 左区间分数 + 右区间分数 + 戳 k 的分数。designgurus+1
这类题中，「对每个 k 切一刀」通常是内层循环导致的 O(n3)O(n^3)O(n3) 时间。
- 两者的关系：遍历 len + 决定是否切 k
这两件事很容易搞混：
「遍历 1~n-len」：是在遍历所有区间的框架，是几乎所有区间 DP 的通用模板。
「中间切一刀」：是在为某个固定区间 [i, j] 写转移时，如果题目结构要求，就需要枚举 k 做切分。olox+1
所以，一般流程是：
1）外层按 len、i、j 遍历所有区间；
2）对于当前区间 [i, j]：
如果是「缩短区间」型，只依赖若干个固定子区间，比如 [i+1, j]、[i, j-1]、[i+1, j-1]；
如果是「切一刀」型，再在内部来一层 for k 把区间切成左右两块。oi-wiki+2
五、如何在实战中判断用哪一种模式
给你一套思考 checklist，遇到新题可以照着问自己：linkedin+2
问题是不是基于「一段连续区间」？
是，则考虑区间 DP。
大区间的答案能不能只通过「缩短一端」得到？
例如只看 [i+1, j]、[i, j-1]、[i+1, j-1] 之类。
如果可以，用「缩短区间」型（模式 A），不需要枚举 k。
最长回文子串的 DP 就是这样：只需要看 [i+1, j-1]。algo+1
大区间的「最后一步操作」，是不是天然对应于「把区间拆成两块」？
比如「最后一次合并/相乘/切割/戳爆」一定是先把 [i, j] 变成 [i, k] 和 [k+1, j] 两段。
如果是，就需要用「中间切一刀」的枚举 k 转移式（模式 B）。
矩阵连乘、合并石子、Burst Balloons 都属于这一类。algo+3
不管选了哪种转移，总之都用「按区间长度 len 从小到大」的遍历顺序，这样保证依赖的子区间先被计算。olox+2
六、回到这道题：你应该怎么在面试里讲
如果是面试里讲「最长回文子串的 DP 解法」，可以按下面结构来组织你的思路：
1）说明这是一个区间 DP 的问题，因为答案是某个子串，且判断「更长子串是不是回文」可以依赖「更短子串」。
2）定义状态：dp[i][j]=dp[i][j] =dp[i][j]= 子串 s[i…j]s[i…j]s[i…j] 是否为回文。
3）初始化：
所有长度为 1 的子串都是回文；
长度为 2 的子串需要 s[i]==s[i+1]s[i] == s[i+1]s[i]==s[i+1]。
4）转移：对 len ≥ 3，若 s[i]==s[j]s[i] == s[j]s[i]==s[j] 且 dp[i+1][j−1]dp[i+1][j-1]dp[i+1][j−1] 为真，则 dp[i][j]=truedp[i][j] = truedp[i][j]=true。
5）遍历顺序：按子串长度 len 从 1 到 n 递增，这样在算 dp[i][j]dp[i][j]dp[i][j] 时，dp[i+1][j−1]dp[i+1][j-1]dp[i+1][j−1] 已经算好。
6）在过程中维护最长回文的长度和起点，最后切一段返回即可。logicmojo+2
