Longest Palindromic Subsequence

'''
LCS variation: Here you have to find the LCS in the string s1 that is for sure and palidrome is something same as right to left so reversing the string and finding LCS between s1 and reversed(s1) will give you an LCS and that exist in the origing string also because LCS property is to match the order so it is for sure, you have picked the valid LCS of the string, now you have found LCS with reversed of the string so the LCS you have got is gonna be palindrom too. so
find LCS between s and reversed(1) and that will be the palindrome LCS.
'''
def fun(s1,s2,n,m,dp):
    if n<0 or m<0:
        return 0
    if dp[n][m]!=-1:
        return dp[n][m]
    if s1[n]==s2[m]:
        dp[n][m]=1+fun(s1,s2,n-1,m-1,dp)
    else:
        dp[n][m]=max(fun(s1,s2,n-1,m,dp), fun(s1,s2,n,m-1,dp))
    return dp[n][m]
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp=[[-1]*len(s) for _ in range(len(s))]
        s2=''.join(reversed(s))
        return fun(s,s2,len(s)-1,len(s)-1,dp)