dynamic programming: longest palindromic subsequence, recurrence relation question
Let 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 = &quot;abb&quot;. 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 &lt;= 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.
Exercise

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 &lt;= j.

What will be the recurrence relations?
Suppose we have computed all T(i,j). What would be the final answer, i.e., the length of the longest palindromic subsequence overall?