Problem Statement

You are given a sequence of black and white horses, and a set of K stables numbered 1 to K. You have to accommodate the horses into the stables in such a way that the following conditions are satisfied:

You fill the horses into the stables preserving the relative order of horses. For instance, you cannot put horse 1 into stable 2 and horse 2 into stable 1. You have to preserve the ordering of the horses.No stable should be empty and no horse should be left unaccommodated.Take the product (number of white horses * number of black horses) for each stable and take the sum of all these products. This value should be the minimum among all possible accommodation arrangements

Example:

`Input: {WWWB} , K = 2 Output: 0

Explanation: We have 3 choices {W, WWB}, {WW, WB}, {WWW, B} for first choice we will get 10 + 21 = 2. for second choice we will get 20 + 11 = 1. for third choice we will get 30 + 01 = 0.

Of the 3 choices, the third choice is the best option.`

If a solution is not possible, then return -1

Problem Link

Arrange II - InterviewBit

Code

int Solution::arrange(string A, int k) {
    
    int n = A.size();
    
    if(n<k)// if no. of horses are less than stables
    return -1;
    
    vector<vector<int>> dp(n+1,vector<int>(k+1,1e9));
   
    dp[0][0] = 0;
    
    for(int j=1;j<=k;j++)//iterating over stables
    {
        
        for(int i=1;i<=n;i++)//iterating over horses
        {
            int b = 0, w = 0;
            for(int l=i;l>=1;l--)
            {
                if(A[l-1]=='B')
                b++;
                else
                w++;
                // keeping i-l+1 horses in the jth stable 
                // and l-1 horses in j-1 stables
                dp[i][j] = min(dp[i][j],dp[l-1][j-1]+b*w);
            }
        }
    }
    
    return dp[n][k];
    
    
}