Given a string , find the length of the longest subsequence that reads the same forward and backward. Example: for "bbbab", the answer is (the subsequence "bbbb").
This is your first interval DP problem. The important point: any palindromic subsequence on depends on whether . If they match, both characters can be part of the palindrome. If not, at least you must be skipped. Before reading on, think: what's the simplest base case? What happens when ?