字符串删除回文串面试题

正文索引 [隐藏]

题目大意:给定一个字符串,每次可以删除一个连续回文,最少几次将删完字符串。






思路

区间DP,dp[l][r] 表示删除字符串 l\cdots r 需要的最小代价。
我们可以将删除回文串的过程看作不断剥离回文串两段的相同字母,因为每一次删除回文串的代价均为 1,我们可以将删除回文串的代价记在删除回文串中心上,剥离非中心的两个相同字母不需要代价。

状态转移方程在普通区间DP合并的基础上,增加了 0 代价剥离区间边缘两个相同字母的情况。
初始化为长度为 1 与长度为 0 的区间代价为 1。

详细思路可以见代码

代码