题目可以很容易看出来是区间型动态规划,但是传统的类似“定义dp[l][r]表示删除s[l,...,r]所需要的最少操作次数”看上去并不好得出状态转移方程。所以需要做一些小小的转换。
可以发现,如果一个子串是回文子串,那么我们仅需一次就可以删除它。所以可以定义:dp[l][r]表示将s[l,...,r]变成回文子串所需要的最少操作次数。
小红有一个长度为n的字符串,这个字符串由26个小写字母组成。
小红可以对这个字符串进行多次操作,每次操作可以把该字符串中一段连续的回文子串删除(单个字符也属于回文串),删除后剩下的串会拼在一起,请问最少需要多少次操作可以将这个字符串删光
第一行,包含一个正整数 T(1≤T≤20)代表测试数据的组数
对于每组测试数据,仅有一行,代表这个字符串。
(1≤n≤500)保证∑n 不超过 3000
对于每组数据输出一行整数,代表小红在进行最少多少次操作后,可以将这个字符串删光
输入
3
mwapd
tvuvv
yxxml
输出
5
3
4