Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Input: "bbbab"
Output: 4
One possible longest palindromic subsequence is "bbbb".Input: "cbbd"
Output: 2
One possible longest palindromic subsequence is "bb".