基于Python實現對求解最長回文子串的動態規劃算法，具體內容如下

1、題目

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為1000。

示例 1：

輸入: "babad"
輸出: "bab"

注意: "aba"也是一個有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

2、求解

對于暴力求解在這里就不再驁述了，著重介紹如何利用動態規劃算法進行求解。

關于動態規劃的含義及用法，請參考鏈接，這篇文章通過漫畫的形式對動態規劃算法進行了詳細而又有風趣的介紹。值得一看。

2.1 算法一

利用常規動態規劃算法，即利用表來存儲每一中回文子串的可能。

基于動態規劃的三要素對問題進行分析，可確定以下的狀態轉換方程：

其中f(i,j)表示當s[i:j]子串是否是回文串。當j-i<=1時，如果s[i] == s[j]則表示s[i:j]為回文串，及f(i,j) = true，否則f(i,j) = false。當j-i > 1時，則判斷 s[i]、s[j]是否相等以及f(i+1, j-1)是否為true，即s[i+1:j-1]是否為回文串，如果為真，則f(i,j) = true

所以就需要一個n*n的二維矩陣用于存儲f(i,j)的值，其中 j in range(0, k)，i in range(0, j+1)，之所以是j+1是因為i可以等于j。

python3代碼如下：

 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 

 采用當前算法，時間復雜度為O(n*n)，空間復雜度為O(n*n)，算法平均耗時大概5~7s

下面介紹空間復雜度為O(n)的算法。

2.2 算法二

算法二是由算法一改良而來，觀察算法一的執行流程如下：

當j>1時，判斷f(i,j)是否為回文子串的操作只與j-1時的的操作相關，即f(i,j) = g(f(i, j-1))，其中j>1，i in range(0, j+1)，所以接下來就變成求解g()函數了。   

用nlist存儲j情況下所有的子串是否為回文子串的標志