题解 | #密码截取#
密码截取
https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
while True: try: s = input() n = len(s) dp = [[False] * n for _ in range(n)] maxlen = 1 for i in range(n-1,-1,-1): for j in range(i,n): if s[i] == s[j]: if j-i <= 1: dp[i][j] = True else: dp[i][j] = dp[i+1][j-1] if dp[i][j] and maxlen < j-i+1: maxlen = j-i+1 print(maxlen) except: break
首先最长回文子串和最长回文子序列是不一样的，两者状态转移不一样
最长回文子序列是 S[i] == s[j]:dp[i+1][j-1]+2 else: max(dp[i+1][j],dp[i][j-1])， dp数组定义的就是i j 这段序列的回文子串长度。
但是两者的填空顺序，和base case 一样， i倒着填，j正着填 ，base case都是 j = i(一个 a) j=i+1(两个 aa) 合并就是 j-i<=1
对于回文子串，dp的定义需要是i,j这段子串是不是回文子串，dp= [[False] *n for _ in range(n)], 因为要求更高， 之后不管是数数量还是 求最长，dp的定义都一样
s[i]!=s[j]时，肯定不是回文子串。那么，当s[i] == s[j]时，需要讨论i和j的情况。第一种是j-i<=1,这种情况包含，a和aa的情况，dp[i][j]为True。
第二种，j-i>=2,判断这一大段是不是回文子串，需要将区间缩小，判断dp[i+1][j-1]是不是回文子串。
投递4399游戏等公司6个岗位 >