5.最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。

1. 双for循环，外层for循环固定回文子串的中心，内层for循环从中心向左右两侧扩展直。需要注意的是要分两种情况，第一种中心只有一个字符(回文子串长度为奇数)，第二种情况中心有两个字符(回文子串长度为偶数)。
2. 动规。dp[i][j]表示下标i到j是否是回文子串，状态转移方程是:if(s[i]=s[j]&&dp[i+1][j-1]==1) dp[i][j]=1;需要注意的一个地方是要求出dp[i][j]需要提前求出dp[i+1][j-1]的值，而后者在前者的左下方，因此遍历顺序是从下到上，从左到右。而且只需要求出dp的上三角矩阵。