dynamic programming: longest palindromic subsequence, recurrence relation question

Question

excel table 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:

excel2

A counterexample would be nice to see.

• 喜欢算法和数学: "just taking T(i,j-1) when T(i,0) != T(0,j)". The part "when T(i,0) != T(0,j)" does not make sense to me. Do you mean "just taking T(i,j-1) when X(i) != X(j)"? Here X is the original array.
• mLstudent33: yes, I put the original array in the 0th row and 0th column like I saw for a sequence alignment DP problem, Needleman-Wunsch algo.

Answer 1

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 = "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.

Exercise

1. Describe the meaning of L(i,j) in that GeeksforGeeks article.

2. 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.

   • 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?

• mLstudent33: L(i,j) is the length of the longest palindromic subsequence from i to j and thus I need to take either max, I get it upon trying out your toy counterexample. Thank you so much!