网上针对这个题，有DP以及Manacher两种算法，这里分享一下dp的另一种做法，时间复杂度大于小于
题目为：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
自己思路：
用动态规划最主要就是状态转移方程。这里采用的状态转移方程如下：首先分两个步骤初始化：（其中
表示在
中最长回文字符串的长度）
1.由于单个字符本身就是回文，因此首先将的初始值全部初始化为1；
2.当时：
，因为重复元素也是回文
动态方程为：
其中，
，判断
是否为回文的方式可以参考函数_isPalindrome。
代码如下：
class Solution(object):
def _isPalindrome(self, s, beg, end, tmp, dp):
j = 0
for i in range(beg, beg+(end-beg)//2+1):
if s[i] != s[end-j]:
return end-tmp+1
j = j + 1
return end-(tmp-dp[tmp])
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s)<=1:
return s
# dp[i]表示s[:i+1]中最长回文字符串的长度
# 初始化dp:单个字符的dp值为1,如果有重复字符,在dp[i-1]基础上加1
dp = [1 for _ in range(len(s))]
for i in range(1,len(s)):
if s[i] == s[i-1]:
dp[i] = dp[i-1]+1
maxVal, maxInd = 0, 0
for i in range(1, len(s)):
if (i-dp[i-1]-1>=0) and (s[i-dp[i-1]-1]==s[i]):
if dp[i-dp[i-1]-1] == 1:
dp[i] = dp[i-1]+2
else:
tmp = i-dp[i-1]-1
beg = tmp-dp[tmp]+1
dp[i] = self._isPalindrome(s[:i+1], beg, i, tmp, dp[:i])
if dp[i]>maxVal:
maxVal = dp[i]
maxInd = i
return s[maxInd-maxVal+1:maxInd+1]
提交结果为：
image.png
如有问题欢迎讨论交流
