eduCF#61 F. Clear the String /// 区间DP 消除连续一段相同字符 全部消完的最少次数

题目描述

给定一个字符串 $s$，你可以进行任意次以下操作：

- 选择一个长度为 $k$ 的连续子串，并将它替换为 $k$ 个相同的字符。
- 操作的代价为 $k-1$。

你需要使得最终的字符串中没有连续相同的字符，求最小代价。

输入格式

第一行包含一个整数 $n$，表示字符串的长度。

第二行包含一个只包含小写字母的字符串 $s$。

输出格式

输出一个整数，表示最小代价。

数据范围

- $1\leq n\leq 1000$

输入样例

8
abbaaccc

输出样例

2

算法

(区间DP,滚动数组) $O(n^3)$

定义 $f[i][j]$ 表示将区间 $[i,j]$ 消除连续一段相同字符的最小代价，然后枚举区间 $[i,j]$ 内划分成哪些区间进行转移即可。

时间复杂度

状态总数 $O(n^2)$，状态转移 $O(n)$，时间复杂度 $O(n^3)$。

空间复杂度

$O(n^2)$。

C++ 代码

滚动数组优化后的代码