A Dynamic programming problem

Question

Can anyone help me find an optimal Dynamic programming algorithm for this problem

On the way to dinner, the CCC competitors are lining up for their delicious curly fries. The N (1 ≤ N ≤ 100) competitors have lined up single-file to enter the cafeteria.

Doctor V, who runs the CCC, realized at the last minute that programmers simply hate standing in line next to programmers who use a different language. Thankfully, only two languages are allowed at the CCC: Gnold and Helpfile. Furthermore, the competitors have decided that they will only enter the cafeteria if they are in a group of at least K (1 ≤ K ≤ 6) competitors.

Doctor V decided to iterate the following scheme:

* 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.

So Doctor V recorded the sequence of competitors for you. Can all the competitors dine? If so, what is the minimum number of groups of competitors to be sent to dinner? Input

The first line contains two integers N and K. The second line contains N characters that are the sequence of competitors in line (H represents Helpfile, G represents Gnold) Output

Output, on one line, the single number that is the minimum number of groups that are formed for dinner. If not all programmers can dine, output -1.

Answer 1

I'd prefer not to solve an SPOJ problem in a practical manner for you, so take the following as an existence proof of a poly-time DP.

For K fixed, the set of strings that can dine is context-free. I'm going to use g and h instead of G and H. For example, for K = 3, one grammar looks like

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

G -> ε | g S G

H -> ε | h S H

The idea is that either there are no diners, or the first diner dines with at least K - 1 others, between any two of which (and the last and the end) there is a string that can dine.

Now use the weighted variant of CYK to find the minimum-weight parse, where nonempty S productions have weight 1, and all others have weight 0. For K fixed, the running time of CYK is O(N³).