最长回文子串
https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-interview-150
动态规划：原问题的解由子问题的解组成，换言之就是在处理大问题之前子问题一定已经处理过了。
回文串就是指一个字符串从前往后读和从后往前读是一样的，字串是连续非空的字符串。
动态规划最重要的就是要挖掘这个问题里面大问题和子问题的关系，ababa是回文串的前提是首尾字符一样并且去除了首尾字符仍然是回文串，即bab也是回文串。
判断更长的字符串是不是回文串的前提是更短的字符串已经被判断过了，因此应该枚举字符串长度，而不是
for i in range(s_len):
for j in range(s_len):
pass
这种形式，因为这种在计算的时候，比如aaaa，如果i=0，j=3，应该根据i=1，j=2即aa这个字串来判断，但是此时这个子串并没有被判断过，因此这样遍历是不行的。
因此要枚举子串的长度和左端点，从小到大，这样才能保证处理更大子串之前小子串已经被处理过了。而且要先枚举字串长度，假如先枚举了左端点仍然会出现处理大子串时小子串还没有被处理过的情况。
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
s_len = len(s)
dp = [[False] * s_len for _ in range(s_len)]
max_len = 0
i_re = 0
j_re = 0
for length in range(1, s_len+1):
for left in range(s_len):
right = length + left - 1
if right >= s_len:
break
if left == right:
dp[left][right] = True
if s[left] == s[right]:
if length < 3:
dp[left][right] = True
else:
dp[left][right] = dp[left + 1][right - 1]
else:
dp[left][right] = False
if dp[left][right] == True and length > max_len:
max_len = length
i_re = left
j_re = right
return s[i_re:j_re+1]
时间复杂度O(n^2)，因为有两重循环。空间复杂度O(n^2)，因为有二维dp数组。