力扣HOT100(53)多维动态规划-最长回文子串

方法动态规划（面试必懂）✅

核心思路（一句话讲透）

利用回文的性质：如果一个子串是回文，那么去掉它首尾两个字符后，剩下的子串也一定是回文。 比如 "ababa" 是回文，去掉首尾的 'a' 后，"bab" 也是回文。

dp 数组定义

用dp[i][j]表示：字符串 s 中从第 i 个字符到第 j 个字符组成的子串（s [i..j]）是否是回文串。

• dp[i][j] = true：s [i..j] 是回文串
• dp[i][j] = false：s [i..j] 不是回文串

状态转移方程

根据回文的性质，我们可以得到：

plaintext

dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

翻译一下：

• 只有当首尾两个字符相等（s [i] == s [j]），并且去掉首尾后的子串（s [i+1..j-1]）也是回文串时，整个子串 s [i..j] 才是回文串。

边界条件（特殊情况）

上面的转移方程适用于子串长度大于 2 的情况，对于长度为 1 和 2 的子串，我们需要单独处理：

1. 长度为 1 的子串：单个字符一定是回文 →dp[i][i] = true
2. 长度为 2 的子串：只要两个字符相等就是回文 →dp[i][i+1] = (s[i] == s