Feb-02-2022, 03:52 PM
(This post was last modified: Feb-02-2022, 06:23 PM by usercat123.)
Hey,
I am trying to code the following problem: given a string find the length of the longest palindromic subsequence and for the input "GATTACAGAT" I get ouput 5 instead of the expected 6. I cannot find the flaw in logic, can somebody help?
I am trying to code the following problem: given a string find the length of the longest palindromic subsequence and for the input "GATTACAGAT" I get ouput 5 instead of the expected 6. I cannot find the flaw in logic, can somebody help?
def solve(w,i,j,dp): #if i > j then the maximum palindromic subsequence is 0 if i > j: return 0 # if i == j then the string is a palindrome of length 1 if i == j: return 1 #if dp[i][j] was solved already, return the value if dp[i][j] != -1: return dp[i][j] #if the characters at i and j are the same we recurse and add 2 to the result if w[i] == w[j]: dp[i][j] = 2 + solve(w,i+1,j-1,dp) return dp[i][j] #if the characters at i and j are not identical the longest palindromic subsequence is equal to that found at either i+1 and j or i and j-1 if w[i] != w[j]: dp[i][j] = max(solve(w,i+1,j,dp),solve(w,i,j-1,dp)) return dp[i][j] def driver(w): dp = [[-1]*len(w)]*len(w) solve(w,0,len(w)-1,dp) print(dp[0][len(w)-1]) w = "GATTACAGAT" driver(w)