8942: DP22 最长回文子序列（Longest Palindromic Subsequence）
[Creator : ]
Description
给定一个字符串 $s$，找到其中最长的回文子序列，并返回该序列的长度。
注：回文序列是指这个序列无论从左读还是从右读都是一样的。
本题中子序列字符串任意位置删除 $k\ (|s|\ge k \ge 0)$ 个字符后留下的子串。
Input
输入一个字符串
Output
输出最长回文子序列
Constraints
$1≤ |s| ≤1,000$
$0 \leq k \leq |s|$
字符串仅包含小写字母
$0 \leq k \leq |s|$
字符串仅包含小写字母
Sample 1 Input
abccsb
Sample 1 Output
4
分别选取第 2、3、4、6 位上的字符组成 “bccb” 子序列是最优解
Sample 2 Input
abcdewa
Sample 2 Output
3
分别选取第一个和最后一个 a，再取中间任意一个字符就是最优解