1、动态规划

1. 定义二维数组dp[length][length]，如果dp[left][right]为true，则表示字符串从left到right是回文子串，如果dp[left][right]为false，则表示字符串从left到right不是回文子串
2. 递推公式

• 如果dp[left+1][right-1]为true，我们判断s.charAt(left)和s.charAt(right)是否相等，
• 如果相等，那么dp[left][right]肯定也是回文子串，否则dp[left][right]一定不是回文子串。

dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1]

3. 初始化

• 如果s.charAt(left)!=s.charAt(right)，那么字符串从left到right是不可能构成子串的，直接跳过即可。
• 如果s.charAt(left)==s.charAt(right)，字符串从left到right能不能构成回文子串还需要进一步判断：
  • 如果left==right，也就是说只有一个字符，我们认为他是回文子串。即dp[left][right]=true（left==right）
  • 如果right-left<=2，类似于"aa"，或者"aba"，我们认为他是回文子串。即dp[left][right]=true（right-left<=2）
  • 如果right-left>2，我们只需要判断dp[left+1][right-1]是否是回文子串，才能确定dp[left][right]是否为true还是false。即dp[left][right]=dp[left+1][right-1]

2、中心点扩散

遍历字符串的每一个字符，然后以当前字符为中心往两边扩散，查找最长的回文子串