A Dynamic programming problem

问题:

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.

回答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³).

回答2:

The subproblem is the minimal groups needed to get everyone to dine for a given state of the line. There are a whole lot of possible line states but only a few that will actually be seen, so your memoization should probably be done with a hash map.

Here's some pseudocode.

int dine(string line){
    if(hashmap.contains(line)){
        return hashmap.get(line);
    }
    if(line.length == 0){
        return 0;
    }
    best = N+1;
    for(i=0;i<line.length;i=j){
        type = string[i];
        j = i+1;
        while(type == string[j]){
            j++;
        }
        if(j-i >= K){
             result = dine(string.substring(0,i-1) + string.substring(j,string.length));
             if(result > 0 && result < best){
                  best = result;
             }
        }
    }
    if(best == N+1){
         hashmap.insert(line, -1);
         return -1;
    }
    else {
         hashmap.insert(line, best+1);
         return best+1;
    }
}

If you already found answer for this line, return that answer. If theres no people in the line, you are already done and you don't need to form any more groups.

Assume you can't form any groups. Then try to prove this wrong by trying out all the contiguous groups of like-minded programmers in the line. If the group is big enough to get picked, see how many more moves it would take to get everyone in the resturaunt after removing this group. Keep track of the least moves needed.

If you couldn't find a way to remove all the groups, return -1. Otherwise, return the least moves needed after removing a group plus one to account for the move you made on this step.

回答3:

How about divide and conquer? Take a (removable) group somewhere near the middle, and the two groups either side of it, say ...HHHGGGGGHHHHH.... - now there's two possibilities. Either those 2 sets of H's dine in the same group, or they don't. If they dine in the same group, then those G's between them must be removed as a group of precisely those G's (so you may as well try that as your first move). If they don't, then you can solve for the left and right sublists separately. Either case, you've got a shorter list to recurse on.