这是leetcode上的一道算法题
对的就是这道题，，困扰了我整整一上午，， 一直也没考虑用动态规划做，， 最终用动态规划把他解决了！
回文串： 正过来和倒过来长的一样， 比如 理总理， 席主席。。。
思想是这样的：
用 dp[i][j] 表示 字符串s的子串s[i:j] 是不是回文串 0表示不是 1表示是
当 i == j 的时候 dp[i][j] 都是1
（意思是s[1:1] s[2:2] 就是一个字符， 字符自己算是个回文子串）
当 i == j-1 的时候，如果 s[i] == s[j] 那dp[i][j] =1 否则为0
（俩字符，这俩是一样的就是回文字符 否则就不是）
其他情况，当 i < j-1 的时候，
如果 dp[i+1][j-1]==1 并且 s[i] == s[j] 的时候 dp[i][i] 就是1
（s[j] 和 s[j] 中间 不包含他俩，原来就是回文的， 他俩还是一个字符，， 那算上这俩也是回文）
否则 dp[i][j] 都是0
（1 s[i]和s[j]中间不包含他俩， 原来不是回文，，那算上他俩也不是回文。
2 如果他俩中间本来是回文 他俩不是一个字符，那算上他俩之后就不是回文）
这样的方式 初始化二维数组， 先把对角线填充上， 然后再把 对角线上一层（两个相邻元素是否相等） 填充上，
然后斜着一层一层填充表就可以。
为了避免重新查表得到最长子串， 可以在填充过程，记录当前最长的子串长度，起始index和结束index
把我的草纸拍下来，大家别嫌弃丑， 填表顺序记录下来 希望对大家有帮助：
我的python代码：
1 class Solution: 2 def longestPalindrome(self, s): 3 """ 4 :type s: str 5 :rtype: str 6 """ 7 length = len(s) # 字符串长度 8 max_length = 1 # 动态规划过程中记录最长回文串长度 默认1是一个字符的情况 9 start = 0 # 最长回文子串的开始位置 默认一开始s[0]自己是一个回文子串10 end = 0 # 回文子串的阶数位置11 # 初始化一个 s长度的二维数组 记录dp过程12 record = [[0 for i in range(length)] for _ in range(length)]13 # record[i][j] 代表 s[i:j] 是不是回文子串14 for i in range(length):15 # 对角线全填充1 代表 一个字符是回文子串16 record[i][i] = 117 # 相邻两个字符如果相同 就记录1 否则记录018 if i >= 1:19 if s[i] == s[i-1]:20 record[i-1][i] = 121 max_length = 222 start = i-123 end = i24 else:25 record[i-1][i] = 026 # 前面两步骤把i j 相差0 和相差1 的情况都在表里填充上了27 # 下面 改用left当作起始位置 right当作结束位置i和j28 # 用i代表left和start的间隔 从2开始到length-1为止29 # 用j从1到length-i30 # 下面开始填充斜对角线31 for i in range(2, length):32 for j in range(length - i):33 left = j 34 right = j + i35 # 如果 s[left+1: right-1] 是回文串 并且 这两个位置字符相同 则s[left:right]也是回文的 否则不是36 if record[left+1][right-1] == 1 and s[left] == s[right]:37 record[left][right] = 138 # 如果发现当前回文串比之前发现的长度长 则更新长度 开始位置和结束位置39 if right - left + 1 > max_length:40 start = left41 end = right42 max_length = right - left + 143 else:44 record[left][right] = 045 # 返回发现的最长回文串46 return s[start: end+1]47 48 49 if __name__ == '__main__':50 s = Solution()51 res = s.longestPalindrome("abbajlhkh")52 print(res)