机试刷题_NC17 最长回文子串【python】

NC17 最长回文子串

动态规划思路
1.定义状态：
设 dp[i][j] 表示字符串 A 从第 i 个字符到第 j 个字符是否为回文子串。
如果是回文子串，dp[i][j] = True，否则为 False。

2.状态转移方程：
如果 A[i] == A[j]，并且 dp[i+1][j-1] 为 True，那么 dp[i][j] = True。
即：dp[i][j] = (A[i] == A[j]) and dp[i+1][j-1]。

3.边界条件：
单个字符一定是回文子串，即 dp[i][i] = True。
两个字符时，如果 A[i] == A[j]，则 dp[i][j] = True。

4.初始化：
初始化所有长度为 1 的子串为回文子串。
初始化所有长度为 2 的子串是否为回文子串。

5.填充 DP 表：
从长度为 3 开始，逐步填充 DP 表，直到长度为 n。

6.结果：
在填充 DP 表的过程中，记录最长的回文子串长度。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型class Solution:def getLongestPalindrome(self , A: str) -> int:# 动态规划n = len(A)if n<=1:return ndp = [[False]*n for i in range(n)]max_len = 1# 单个字符一定是回文子串for i in range(n): dp[i][i] = True# 检查长度为2的子串for i in range(n-1): if A[i]==A[i+1]:dp[i][i+1] = Truemax_len = 2# 检查长度大于2的子串for length in range(3,n+1): #子串长度从3到nfor i in range(n-length+1): #子串起始位置j = i+length-1          #子串结束位置if A[i]==A[j] and dp[i+1][j-1]:dp[i][j] = Truemax_len = max(max_len,length)return max_len