题解 | #最长回文子序列#
最长回文子序列
http://www.nowcoder.com/practice/c7fc893654b44324b6763dea095ceaaf
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string 一个字符串由小写字母构成，长度小于5000
# @return int
#
class Solution:
def longestPalindromeSubSeq(self , s ):
# write code here
if s == s[::-1]:
return len(s)
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
for i in range(len(s) - 2, -1, -1):
for j in range(i + 1, len(s)):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][-1]
投递大疆等公司7个岗位
查看30道真题和解析