屏幕快照 2019-02-17 下午4.01.57.png
class Solution(object):
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
N=len(s)
dp=[[0]*N for _ in range(N)]
for i in range(N):
dp[i][i]=1
for i in range(N-2,-1,-1):
for j in range(i+1,N):
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][N-1]
网友评论