解题思路1：
假设字符串s的长度为len, 则先创建一个长度为len * len的全0数组M，用来存放最大回文串的长度。
M[i][j]表示以下标i开始，j结束，则共有两层循环，外层循环j的取值为（0，len), 内层循环i的取值为（0，j+1),有如下的状态转移方程：
当i=j时，初始化数组M，即只有1个字符时，是回文字符串。
下面均针对s[i]==s[j]的情况讨论：
当j>i时 如果j与i只差1，则代表有两个重复的字符，如bb， 也是回文字符串，M[i][j]=2.
当j>1时，j-i>1, 则需比较其子字符串是否是回文字符串（M[i+1][j-1]>0),若是，则设置M[i][j]的长度为子回文串长度+2，否则设置M[i][j]=0
参考代码：
import numpy as np class Solution(object): # 动态规划 leetcode最后一个用例会超出时间限制 def longestPalindrome(self, s): """ :type s: str :rtype: str """ if len(s) <=1: return s # 保存回文长度的矩阵 matrix = np.zeros((len(s),len(s))) max_len = 0 # 动态规划求解 for j in range(0,len(s)): for i in range(0,j+1): if i == j: matrix[i][j] = 1 # 仅有1个字符时 else: if s[i] == s[j]: if j-i == 1: matrix[i][j] = 2 elif matrix[i+1,j-1] > 0: matrix[i][j] = matrix[i+1,j-1] + 2 else: matrix[i][j] = 0 else: matrix[i][j] = 0 print(matrix) logest_len= int(np.max(matrix)) # print(np.argmax()) row = np.argmax(matrix)//len(s) col = np.argmax(matrix)%len(s) return s[row:row+logest_len]解题思路2：
由于该方法计算了每个回文字符串的长度，增加了运行时间，为了减少时间，我们将M设置为bool数组，用来保存是否为回文串的状态。
i和j的含义与前面一致，则状态转移方程变为：
if语句将前面公式的前三项糅合在一起了，只要满足if的条件，则即为回文字符串。否则不是回文字符串。
该方法注意保存最长回文字符串的大小和最长回文串的位置。
参考代码：
import numpy as np class Solution(object): # 修改后的动态规划算法 def longestPalindrome(self, s): """ :type s: str :rtype: str """ if len(s) <=1: return s # 保存状态的矩阵 matrix = np.zeros((len(s),len(s)),dtype=bool) max_len = 0 # 最长回文字符串的大小 loc = (0,0) # start,end 最长回文串的位置 # 动态规划求解 for j in range(0,len(s)): for i in range(0,j+1): if s[i]==s[j] and ( j-i<2 or matrix[i+1][j-1]): matrix[i][j] = True if max_len < j-i+1: max_len = j-i+1 # 长度 loc = (i,j) # 位置 return s[loc[0]:loc[0]+max_len]
