P15101

最长回文子序列

难度 5 级 小学 动态规划入门 区间DP
讨论 统计 20通过 32提交 62.5%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给定字符串s,从其中取出部分字符,并保持前后顺序不变,组成的字符串成为原字符串的子序列。例如在abcdbca中,abc、acc、acdca等均为子序列。如果子串满足回文规律,则称回文子序列。 求其最长回文子序列的长度。

输入

一个字符串,长度不大于1000.

输出

最长回文子序列长度。

样例

样例 1
输入
abcdbca
输出
5

提示

样例中,abcdbca的最长回文子序列为abdba、acdca、acbca,长度均为5.

来源

动规专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交