第2题-塔子哥删字符 - Problem Detail

ID: 837

Difficulty: 9

所属公司 : 拼多多

时间 :2024年3月24日

题目描述

小红有一个长度为 $n$ 的字符串,这个字符串由26个小写字母组成。

小红可以对这个字符串进行多次操作,每次操作可以把该字符串中一段连续的回文子串删除(单个字符也属于回文串),删除后剩下的串会拼在一起,请问最少需要多少次操作可以将这个字符串删光

题目可以很容易看出来是区间型动态规划，但是传统的类似“定义 $dp[l][r]$ 表示删除 $s[l,...,r]$ 所需要的最少操作次数”看上去并不好得出状态转移方程。所以需要做一些小小的转换。

可以发现，如果一个子串是回文子串，那么我们仅需一次就可以删除它。所以可以定义： $dp[l][r]$ 表示将 $s[l,...,r]$ 变成回文子串所需要的最少操作次数。