I added some prints so I could watch execution.
def solve(w,i,j,dp):
print(w, i, j, w[i:j+1])
#if i > j then the maximum palindromic subsequence is 0
if i > j:
print("i > j")
return 0
# if i == j then the string is a palindrome of length 1
if i == j:
print("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]:
print(f"w[{i}] == w[{j}]", dp[i][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]:
print(f"w[{i}] != w[{j}]", dp[i][j])
dp[i][j] = max(solve(w,i+1,j,dp),solve(w,i,j-1,dp))
return dp[i][j]Finally think I have this figured. You start at the outside and work your way inward until there are no more matches. Then you start unwinding the recursion and begin again moving inward form different starting points. Neat!
bowlofred nailed the problem. When I changed the dp initializer to this:
dp = [[-1]*len(w) for _ in range(len(w))]
I saw this line printed out for the very first time:
GATTACAGAT 0 7 GATTACAG
i = 0 and j = 7 are the starting points you need to find "GATTAG".
To make sure I understood it I rewrote it to less C-like and more Python-like.
def solve(word, cache=None):
"""
Return length of longest palindrome sequence contained in word.
Letters in the palindrome sequence are sampled in order from the original word. "STATS" is
a valid palindrome of "STARTS" because it only removes letters.
"""
if cache is None:
# cache is dictionary of solved sequences. It eliminates recomputing
# palindrome lengths for subsequences that were already solved.
cache = {}
if len(word) < 2:
# End of recursion. Cannot shrink word any more
return len(word)
if word in cache:
# End of recursion. Already solved this sequence
return cache[word]
# This is where the work is done.
if word[0] == word[-1]:
# If the first and last letters of word match we have a palindrome
# of length 2 plus the palindrome length of word with the first and last
# letters removed.
cache[word] = 2 + solve(word[1:-1], cache)
else:
# If the letters do not match compute the the palindrome length of word
# with the first letter removed and word with the last letter removed.
# Use the max length as the length of word.
cache[word] = max(solve(word[1:], cache), solve(word[:-1], cache))
return cache[word]
print(solve("GATTACAGAT"))I don't know if it is easier to read because it is Python or if it is just easier for me to read because I know what is happening now.
I also tried a brute force solution.
import itertools
def palindromes(word):
"""Return palindrome sequences contained in word. The sequence
can skip letters between the start and end characters.
"""
# For all possible lengths
for count in range(2, len(word)+1):
even = count % 2 == 0
# for all combinations of this length
for combo in itertools.combinations(word, r=count):
a = count // 2 - 1
b = a + 1 if even else a + 2
# yield sequence if it is a palindrome
if combo[:a+1] == combo[b:][::-1]:
yield ''.join(combo)
# Get all the palindromes. Sort by length (reverse) and then alphabetically
words = list(palindromes("GATTACAGAT"))
words.sort(key=lambda x: (-len(x), x))
print(words)The brute force method is painfully inefficient. The time required to solve doubling with each additional letter, Solving "ABLE WAS I ERE I SAW ELBA" takes less than a millisecond using dvdlly's method. Using the brute force method it takes 10 seconds.
