leetcode 5.最长回文子串（中等，动态规划）

题目：

中心扩展法：

以例子"bababb"来介绍；

找到回文串的中心，有两种情况，第一种是bab这种情况，第二种是bb这种情况；

因此找的bab这种情况的中心有n个(中心为a)，bb这种情况的中心个数为n - 1(中心为b与b之间的间隙）, 因此中心数目一共是2n - 1;

代码逻辑：

遍历每一个中心点，查找回文子串；

对于两种中心点，依次以中心点开始向两边扩展，判断中心点周围的值是否相等，如果相等，继续进行扩展；否则，返回当前回文子串；

代码如下：

class Solution:
    def longestPalindrome(self, s):

    	size = len(s)
    	if size < 2:
    		return s


    	maxLen = 1

    	res = s[0:1]
    	#枚举中心点
    	for i in range(0,len1 - 1):

    		oddstr = self.__center_spread(s, size, i, i)
    		evenstr = self.__center_spread(s, size, i, i + 1)

    		maxLenStr = oddstr if len(oddstr) > len(evenstr) else evenstr

    		if len(maxLenStr) > maxLen:

    			maxLen = len(maxLenStr)
    			res = maxLenStr

    	return res





    def __center_spread(self, s, size, left, right):

    	#left = right的时候，此时回文中心是一个字符，回文串的长度是奇数
    	#right = left + 1的时候，此时回文中心是一个空隙。回文串的长度是偶数

    	i = left
    	j = right
    	while i >= 0 and j < size:
    		if s[i] == s[j]:
    			i -= 1
    			j += 1
    		else:
    			break


    	return s[i + 1: j]

上述算法有重复解的情况，

动态规划法：

动态规划法的思路，如果有重复的情况，可以考虑是否应该采用动态规划，因为动态规划是自底向上，对于计算过的用空间保存下来，下一次遇到相同计算，直接取出即可；

因此动态规划是以空间换时间的做法；

状态转移方程的设置：

$dp[j][i]$dp[j][i]表示在一个字符串中从下标j到下标i是否是一个回文字串， 如果是一个回文子串，置1；

则$dp[j][i]$dp[j][i]是一个二维度的数组，初始化除了对角线元素为了1外（因为$dp[j][j]$dp[j][j] = 1)，其他均为0；

建立上述的转移方程，可以减少计算量，即已经计算过的会保存在dp数组中；

其中动态规划的老套路，两层for循环实现，第二层for循环的边界是第一层for循环的值；

动态规划模版：

for i in range(1,len(s)):
  for j in range(0,i):
    #状态转移条件
    #进行状态转移

在本题中，对于状态转移方程，$dp[j][i]$dp[j][i]表示从j到i的子串是否是回文子串，因此第一层for循环是i；第二层for循环是j；

并且，$dp[i][i]$dp[i][i] = 1,

边界条件：

$dp[j][i]$dp[j][i], (i = j), $dp[j][i]$dp[j][i] = 1;

$dp[j][i]$dp[j][i], (i = j + 1) , 如果s[j] = s[i], 则$dp[j][i]$dp[j][i] = 1,否则为0；（表示bb）（ba）这样的子串

$dp[j][i]$dp[j][i], (i = j + 2), 如果s[j] = s[i], 则$dp[j][i]$dp[j][i] = 1,否则为0；（表示bab）（bac）这样的子串

其中这三种边界情况，满足i - j < 3；

代码如下：

class Solution:
    def longestPalindrome(self, s):

    	m = len(s)

    	if m < 2:
    		return s

    	#以空间换时间，创建一个dp数组
    	dp = [[0 for i in range(m)] for j in range(m)]

    	start  = 0#表示字符串的开始下标
    	end = 1#表示字符串的结束下标
    	maxlength = 1

    	for i in range(1, m):
    		for j in range(0, i + 1):

    			if s[j] == s[i]:

    				#没有子串的情况
    				if i - j < 3:

    					dp[j][i] = 1

    				else:
    					dp[j][i] = dp[ j + 1][i - 1]


    			if dp[j][i]:
    				#判断字符串的长度
    				if (i - j + 1) >maxlength:
    					maxlength = i - j + 1
    					start = j
    					end = i + 1


    	return s[start:end]

代码优化, 第二层for循环的边界改为i，因为对于$dp[i][i]$dp[i][i]为最大长度子串的情况，可以不用赋值，最后都会返回res[0:1]：

class Solution:
    def longestPalindrome(self, s):

    	m = len(s)



    	if m < 2:
    		return s

    	#以空间换时间，创建一个dp数组
    	dp = [[0 for i in range(m)] for j in range(m)]

    	start  = 0
    	end = 1
    	maxlength = 1

    	for i in range(1, m):
    		for j in range(0, i):

    			if s[j] == s[i]:

    				#没有子串的情况
    				if i - j < 3:

    					dp[j][i] = 1

    				else:
    					dp[j][i] = dp[ j + 1][i - 1]


    			if dp[j][i]:
    				#判断字符串的长度
    				if (i - j + 1) >maxlength:
    					maxlength = i - j + 1
    					start = j
    					end = i + 1


    	return s[start:end]