Python solution recursive

programming
Tags: #<Tag:0x00007f1826d37bc0>

#1

class Solution:
# @param A : string
# @return an integer
def solve(self, A):
import sys
sys.setrecursionlimit(100000)
l=len(A)
dp=[[-1]*l for i in range(l)]
B=A[::-1]
def lcs(i,j):
if i==l or j==l:
return 0
if dp[i][j]!=-1:
return dp[i][j]
if A[i]==B[j]:
rr=1+lcs(i+1,j+1)
dp[i][j]=rr
return rr
else:
rr=max(lcs(i+1,j),lcs(i,j+1))
dp[i][j]=rr
return rr
return lcs(0,0)