algorithm - 一个动态规划问题

Question

谁能帮我找到this problem 的最佳动态规划算法

在去吃晚饭的路上，CCC 的参赛者正在排队享用美味的 curl 薯条。 N(1≤N≤100)名选手排成单行进入食堂。

负责 CCC 的 V 博士在最后一刻意识到，程序员只是讨厌站在使用不同语言的程序员旁边排队。值得庆幸的是，CCC 只允许使用两种语言:Gnold 和 Helpfile。此外，参赛者已经决定，只有在至少有 K(1 ≤ K ≤ 6)名参赛者的情况下，他们才会进入自助餐厅。

V 博士决定迭代以下方案:

* He will find a group of K or more competitors who use the same language standing next to each other in line and send them to dinner.
* The remaining competitors will close the gap, potentially putting similar-language competitors together.

所以V博士给大家记录下了参赛选手的顺序。所有的参赛者都可以用餐吗？如果是这样，最少要派多少组参赛者去吃饭？输入

第一行包含两个整数N和K。第二行包含N个字符，即一行中参赛者的顺序(H代表Helpfile，G代表Gnold)输出

在一行中输出单个数字，即为晚餐组成的最小组数。如果不是所有的程序员都能吃饭，输出-1。

Answer 1

我不想以实际的方式为您解决 SPOJ 问题，因此将以下内容作为多时间 DP 的存在证明。

对于固定的K，可以用餐的字符串集合是上下文无关的。我将使用 g 和 h 而不是 G 和 H。例如，对于 K = 3，一种语法看起来像

S -> ε | g S g S g S G | h S h S h S H

G -> ε | g S G

H -> ε | h S H

这个想法是，要么没有用餐者，要么第一个用餐者与至少 K - 1 个其他人一起用餐，在其中任何两个(以及最后一个和最后一个)之间有一个可以用餐的字符串。

现在使用 CYK 的加权变体找到最小权重解析，其中非空 S 产生式的权重为 1，所有其他产生式的权重为 0。对于固定的 K，CYK 的运行时间为 O(N³)。