DAY22 2026.05.12
LeetCode5 最长回文子串 [双指针、多维动态规划]
方法一：中心扩散法。一遍for循环遍历字符串s，选取i为中心，用left和right双指针向两侧扩散，判断子串是否为回文子串，记录最长回文子串长度和起点。注意奇数个的情况和偶数个的情况都要考虑到
方法二：动态规划法。用boolean dp[left][right]表示字符串从left到right这段是否为回文子串
当s[left] == s[right]时，有三种情况：
- 下标left与right相同，同一个字符如a，当然为回文子串
- 下标left与right相差1，如aa，也是回文子串
- 下标left与right相差大于1时，例如cabac，此时要确定是不是回文子串，就要判断dp[left+1][right-1]是否为true
初始状态，left=right时，dp[left][right]=true，其他全初始化为false
由递推公式发现，情况三dp[left][right]是由左下角dp[left+1][right-1]推导而来，所以应该从下到上、从左到右进行遍历