Find the longest palindromic subsequence in . observation: LPS = LCS. Why? A palindrome reads the same forwards and backwards.
So the common subsequence between and its reverse is palindromic. Example: . Reverse: "babbb". LCS = "bbbb" with length . Alternative: direct DP with = LPS of . Transition: if , extend; else take max of excluding either end.