= the length of the longest palindromic subsequence in . Why this formulation? Palindromes have a natural interval structure. They're defined by their endpoints. When you add characters at both ends, you need to know the answer for the inner substring.
Base cases: (a single character is a palindrome of length ). (empty range, used when in the recurrence). The final answer is , covering the entire string. Fill the table by increasing interval length, so smaller intervals are ready when you need them.