一、完整代码（精简注释）
class Solution { public: string longestPalindrome(string s) { int n = s.length(); int maxlen = 1; // 最长回文子串的长度 int start = 0; // 最长回文子串的起始下标 if (n < 2) return s; // dp[i][j] 表示 s[i...j] 是否为回文子串 vector<vector<bool>> dp(n, vector<bool>(n, false)); // 先遍历右端点，再遍历左端点 for (int j = 0; j < n; j++) { for (int i = 0; i <= j; i++) { // 左右字符相等，才可能是回文 if (s[i] == s[j]) { // 长度 <= 3 或中间子串是回文 if (j - i <= 2 || dp[i+1][j-1]) { dp[i][j] = true; int len = j - i + 1; // 更新最长回文子串 if (len > maxlen) { start = i; maxlen = len; } } } } } // 截取最长回文子串 return s.substr(start, maxlen); } };二、动态规划五步总结
1. 确定 dp 数组及下标含义
vector<vector<bool>> dp(n, vector<bool>(n, false));dp[i][j]表示字符串 s 从下标 i 到 j 的子串是否为回文。
dp[i][j] = true：是回文子串。dp[i][j] = false：不是回文子串。
例如：
s = "ababa" dp[0][4] = true // ababa dp[1][3] = true // bab dp[0][1] = false // ab2. 确定状态转移方程
判断s[i...j]是否为回文，需要考虑两种情况。
情况一：左右字符不相等
s[i] != s[j]说明当前子串一定不是回文，dp[i][j]保持 false。
情况二：左右字符相等
s[i] == s[j]此时还需要判断中间子串是否为回文。
如果子串长度小于等于 3，只需要左右字符相等即可。
"a" 长度为1 "aa" 长度为2 "aba" 长度为3如果子串长度大于 3，则需要判断中间部分：
dp[i+1][j-1]因此状态转移为：
if (s[i] == s[j]) { if (j - i <= 2 || dp[i+1][j-1]) { dp[i][j] = true; } }注意：
j - i <= 2等价于子串长度小于等于 3，因为子串长度是j - i + 1。
3. 初始化 dp 数组
vector<vector<bool>> dp(n, vector<bool>(n, false));首先将所有状态初始化为 false。
对于单个字符：
i == j由于字符与自身相等，并且满足j-i <= 2，因此会自动将：
dp[i][i] = true;所以不需要额外初始化对角线。
另外：
int maxlen = 1; int start = 0;表示初始最长回文子串为第一个字符，长度为 1。
4. 确定遍历顺序
for (int j = 0; j < n; j++) { for (int i = 0; i <= j; i++) { // 状态转移 } }采用先遍历右端点 j，再遍历左端点 i 的方式。
原因是：
计算dp[i][j]时，需要依赖：
dp[i+1][j-1]也就是说，当前子串是否为回文，依赖于中间子串是否为回文。
而中间子串的右端点是j-1，比当前右端点 j 小。
因此先从小到大遍历 j，能够保证依赖的状态已经计算完成。
核心：先计算短子串，再利用短子串的结果判断长子串。
5. 举例推导 dp 数组
假设：
s = "babad";下标：
下标： 0 1 2 3 4 字符： b a b a d当 j = 2，i = 0 时：
s[0...2] = "bab"判断：
s[0] == s[2] // b == b，成立 j - i <= 2 // 2 <= 2，成立因此：
dp[0][2] = true;计算长度：
len = 2 - 0 + 1 = 3;由于：
len > maxlen更新：
start = 0; maxlen = 3;之后找到"aba"时，其长度同样为 3，因此不会更新。
最终返回：
s.substr(0, 3); // "bab"三、复杂度分析
时间复杂度：O(n²)
两层循环枚举左右端点，每个 dp 状态只需要常数时间进行判断。
空间复杂度：O(n²)
创建了一个 n × n 的二维 bool 数组存储回文状态。
四、核心总结（适合 CSDN 笔记）
本题使用二维动态规划，利用较短子串的回文状态判断较长子串是否为回文。
dp[i][j] 表示从下标 i 到 j 的子串是否为回文。
当 s[i] != s[j] 时，当前子串一定不是回文。
当 s[i] == s[j] 时，如果子串长度小于等于 3，则当前子串一定是回文；否则需要判断中间子串 dp[i+1][j-1] 是否为 true。
初始化二维 dp 数组为 false，单个字符的回文状态会在遍历过程中自动更新。
遍历顺序为先枚举右端点 j，再枚举左端点 i，保证计算当前状态时，依赖的中间子串状态已经计算完成。
每找到一个回文子串，就计算其长度
len = j-i+1。如果超过 maxlen，则更新最长长度 maxlen 和起始下标 start。最终使用
s.substr(start, maxlen)截取最长回文子串。
最重要的三个知识点
① 回文判断
if (s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1])) { dp[i][j] = true; }② 最长长度更新
int len = j - i + 1; if (len > maxlen) { start = i; maxlen = len; }③ 截取字符串
return s.substr(start, maxlen);一句话总结：先判断左右字符是否相等，再判断中间子串是否为回文，同时记录出现过的最长回文子串。
