题目求助

· · 算法·理论

信息萌新求助！ 遇到一道神秘dp题,网站上没找到原题和题解，有没有大佬能看一下帮助一下，十分感谢!

有一个长度为 n 的字符串，字符串均由英文小写字母组成。每次可以将一个长度不大于 l 的子串修改成同一种字母，问至少修改多少次可以使字符串最多含有 k 段。

连续的只含同一种字母的子串被称为一段。比如说， aaabbccaaa 一共含有 4 段。

输入格式 输入包含两行。

第一行三个整数 n ，l ，k 。

第二行一个字符串。

输出格式 一行一个数表示答案。

样例输入1 3 1 1 aba 样例输出1 1 样例输入2 5 2 2 ababa 样例输出2 2 样例输入输出3 见附加文件。

数据范围 对于 30% 的数据，保证 1≤n≤20 ，字符串由 a, b 组成。

对于 60% 的数据，保证 1≤n≤1000 。

对于 100% 的数据，保证 1≤n≤100000 , 1≤l≤n , 1≤k≤10 ，字符串均由小写字母组成。