python实现对求解最长回文子串的动态规划算法

 k = len(s) # 计算字符串的长度 
 matrix = [[0 for i in range(k)] for i in range(k)] # 初始化n*n的列表 
 logestSubStr = "" # 存储最长回文子串 
 logestLen = 0 # 最长回文子串的长度 
 
  for j in range(0, k): 
   for i in range(0, j+1): 
    if j - i <= 1: 
     if s[i] == s[j]: 
      matrix[i][j] = 1   # 此时f(i,j)置为true 
      if logestLen < j - i + 1: # 将s[i:j]的长度与当前的回文子串的最长长度相比 
       logestSubStr = s[i:j+1] # 取当前的最长回文子串 
       logestLen = j - i + 1 # 当前最长回文子串的长度 
    else: 
     if s[i] == s[j] and matrix[i+1][j-1]: # 判断 
      matrix[i][j] = 1 
      if logestLen < j - i + 1: 
       logestSubStr = s[i:j+1] 
       logestLen = j - i + 1 
  return logestSubStr 

k = len(s) 
 olist = [0] * k # 申请长度为n的列表，并初始化 
nList = [0] * k # 同上 
logestSubStr = "" 
 logestLen = 0 
 
  for j in range(0, k): 
   for i in range(0, j + 1): 
    if j - i <= 1: 
     if s[i] == s[j]: 
      nList[i] = 1 # 当 j 时，第 i 个子串为回文子串 
      len_t = j - i + 1 
      if logestLen < len_t: # 判断长度 
       logestSubStr = s[i:j + 1] 
       logestLen = len_t 
    else: 
     if s[i] == s[j] and olist[i+1]: # 当j-i>1时，判断s[i]是否等于s[j]，并判断当j-1时，第i+1个子串是否为回文子串 
      nList[i] = 1 # 当 j 时，第 i 个子串为回文子串 
      len_t = j - i + 1 
      if logestLen < len_t: 
       logestSubStr = s[i:j + 1] 
       logestLen = len_t 
   olist = nList  # 覆盖旧的列表 
   nList = [0] * k # 新的列表清空 
  return logestSubStr