🐰😺📜 兔猫信奥学院的回文子序列探险 📜😺🐰

在信奥学院的秘典殿堂里，加菲老师拿出一卷古老魔典，上面刻着一行神秘文字。老师告诉小兔和小猫：“你可以删去一些字符，但不能改变剩余字符的相对顺序，来寻找一段最长的回文子序列——正着读和反着读都相同的字符序列。你们能告诉我，这条神秘文字中最长的回文子序列有多长吗？”

输入格式

输入仅包含一行字符串 s。

• $1\le |s|\le 10000$
• $s$ 仅由小写英文字母组成。

输出格式

输出一个整数，表示最长回文子序列的长度。

样例 1

bbbab

4

• 解释：
  一个最长的回文子序列是 “bbbb”，长度为 $4$。

样例 2

cbbd

2

• 解释：
  一个最长的回文子序列是 “bb”，长度为 $2$。

🎓 加菲老师寄语：
将最长回文子序列转为“与自身反转串求 LCS”是一种优雅技巧，既能压缩空间至 $O(n)$，又保持 $O(n^2)$ 时间。掌握它，你将在更多序列比对与编辑距离问题中游刃有余。持续探秘，祝学习进步！