最长回文子串题目来源：https://leetcode-cn.com/problems/longest-palindromic-substring/题目给定一个字符串s，求s文子串中最长的回文子串。您可以假设s的最大长度为1000。示例1：输入：“babad”输出：“bab”注意：“aba”也是一个有效答案。例2：输入："cbbd"输出："bb"动态规划的解题思路；如果是单个字符，则必须是回文；如果字符串的第一个字符和最后一个字符不同，则一定不是回文；如果首末字符相同，则继续判断内部子串；对于内部子串，要考虑边界问题。如果s[i]和s[j]是同一个字符，去掉第一个和最后一个s[i]和s[j]，继续判断。[i+1,j-1]对于这个区间，需要注意的是可能无法形成区间，即长度小于2时。换算成公式：j-1-(i+1)+1<2可以得到j-i<3。这也就意味着，当s[i,j]的长度为2或3时，只需要判断首末字符相同即可得出结论。根据上面得到的j-i<3，可以对结果进行如下判断和展开：a．如果s[i+1,j-1]的区间只有1个字符，符合单个字符为回文的规则，直接判断结论b。如果s[i+1,j-1]为空，则子串s[i,j]为回文子串。代码实现类解决方案：deflongestPalindrome(self,s:str)->str:length=len(s)#如果字符串长度小于2，直接返回，单个字符为回文iflength<2:returns#longestchildStringlength，至少为1，单个字符为回文max_sub_len=1#最长子串起始位置start=0#动态规划dp=[[Falsefor_inrange(length)]for_inrange(length)]#single字符为回文，设置矩阵的对角线为Trueforiinrange(length):dp[i][i]=True#遍历字符串，比较子串头尾是否相同#如果是相同，继续比较内部子串#当子串首末字符相同且子串长度为2或3时，可直接判定为回文子串forjinrange(1,length):foriinrange(0,j):#首末字符相同，继续比较ifs[i]==s[j]:#beginning和end相同，子串长度小于等于3，可以直接下结论ifj-i<3:dp[i][j]=Trueelse:#否则继续比较内部子串dp[i][j]=dp[i+1][j-1]else:continueifdp[i][j]:#获取此时回文子串的长度cur_sub_len=j-i+1ifcur_sub_len>max_sub_len:max_sub_len=cur_sub_len#重置子串的起始位置start=ireturns[start:start+max_sub_len]以上是这篇文章的效果主要内容，虽然跑出来的结果不是很理想，但是这道题动态规划的大体思路是这样的。后续考虑改进方法来实现这个问题。欢迎关注微信公众号《书所集录》
