題目描述

給定一個由小寫字母組成的字符串，求出它的最長回文子序列的長度。回文是指正反讀都一樣的字符串，例如"abba"和"racecar"。子序列是指從原字符串中刪除零個或多個字符後得到的字符串，例如"abc"的子序列有"a",“b”,“c”,“ab”,“ac”,“bc"和"abc”。

範例：輸入： bbbab 輸出： 4 解釋：最長回文子序列是"bbbb"，長度為4。

輸入格式

一行字符串，只包含小寫字母。

限制：字符串的長度不超過1000。

一個正整數，表示最長回文子序列的長度。

["bbbab","abba","racecar","abca","abcd"]

["4","4","7","3","1"]