Moving from top left down the column then over to the right column, taking ideas from here: https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/
I want to restate the question at the top of the Excel table.
Why do I need to max from T(i,j-1) and T(i+1,j)? Can't you just take what's in T(i,j-1)?
I changed the input slightly and I still get the right answer just taking T(i,j-1) when T(i,0) != T(0,j)
Edited:
A counterexample would be nice to see.
T(i,j) = T(i,j-1) when L(i) != L(j)You could be wrong if you take T[0, n-1] as the final answer as in the article on GeeksforGeeks. For example, let X = "abb". Then T[0, n-1] = 1 while the longest palindromic subsequence is bb with length 2.
You are right if you take the maximum of T[i,n-1] as the final answer, where i goes through all valid indices, i.e., from 0 to n-1 and n is the length of the given string X.
What is happening?
We need to understand/specify the meaning of T(i,j). We can let T(i,j) denote the length of the longest one among all subsequences that start at index i and end no later than index j, where i <= j. Then it is correct that T(i,j) = T(i,j-1) when X(i) != X(j), since any palindromic subsequence that start at index i cannot end at index j, i.e., it must end no later than index j-1.
Describe the meaning of L(i,j) in that GeeksforGeeks article.
Suppose we let T(i,j) denote the length of the longest one among all subsequences that start at index i and end at index j, where i <= j.
T(i,j). What would be the final answer, i.e., the length of the longest palindromic subsequence overall?