2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "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. $\endgroup$ – John L. Apr 17 at 22:29
  • $\begingroup$ 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. $\endgroup$ – mLstudent33 Apr 18 at 2:12
1
$\begingroup$

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?
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ – mLstudent33 Apr 18 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.