[特殊字符] LeetCode 5. 最长回文子串（C语言 | 动态规划详解）

一、题目描述给你一个字符串s找到其中最长的回文子串。示例输入: s babad 输出: bab 解释: aba 也是答案输入: s cbbd 输出: bb 二、解题思路动态规划虽然这题最优雅的做法是「中心扩展」但二维 DP 是经典区间 DP 模板题非常适合训练思维。✅ 1. 状态定义我们定义dp[i][j] 1 表示 s[i...j] 是回文串 dp[i][j] 0 表示不是回文串✅ 2. 状态转移方程关键条件s[i] s[j] (j - i 2 || dp[i1][j-1])解释条件含义s[i] s[j]两端字符必须相等j - i 2长度为 1 或 2如 a / aadp[i1][j-1]中间子串必须是回文✅ 3. 遍历顺序重点⚠️ 这是本题最容易错的地方因为dp[i][j]依赖dp[i1][j-1]所以必须从下往上从左往右代码顺序for (int i n - 1; i 0; i--) { for (int j i; j n; j) {✅ 4. 记录最长回文在更新dp[i][j]的同时如果是回文 长度更长 → 更新答案 三、完整代码C语言#include stdlib.h #include string.h char* longestPalindrome(char* s) { int n strlen(s); if (n 0) return ; int dp[1000][1000] {0}; int start 0; int maxLen 1; for (int i n - 1; i 0; i--) { for (int j i; j n; j) { if (s[i] s[j]) { if (j - i 2) { dp[i][j] 1; } else if (dp[i 1][j - 1]) { dp[i][j] 1; } } if (dp[i][j] (j - i 1 maxLen)) { maxLen j - i 1; start i; } } } char* res (char*)malloc(maxLen 1); strncpy(res, s start, maxLen); res[maxLen] \0; return res; }⚠️ 四、常见错误总结❌ 1. 遍历顺序写错错误写法for (i 0; i n; i) 会导致dp[i1][j-1]未计算❌ 2. 忘记处理长度 1 / 2j - i 2 这是核心边界条件❌ 3. 回文长度计算错误正确len j - i 1❌ 4. 返回字符串未加 \0res[maxLen] \0; 五、复杂度分析项目复杂度时间复杂度O(n²)空间复杂度O(n²) 六、方法对比方法时间空间推荐度中心扩展O(n²)O(1)⭐⭐⭐⭐⭐动态规划O(n²)O(n²)⭐⭐⭐ManacherO(n)O(n)⭐⭐⭐⭐ 七、总结 本题本质是区间 DP关键点就三句话定义dp[i][j]利用dp[i1][j-1]注意遍历顺序从下往上 八、进阶思考如果你想进一步提升✅ 中心扩展面试最常用 Manacher线性时间硬核加分