Arrange II

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 1*0 + 2*1 = 2.
for second choice we will get 2*0 + 1*1 = 1.
for third choice we will get 3*0 + 0*1 = 0.

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

If a solution is not possible, then return -1

public class Solution {
    public int arrange(String str, int stables) {
        int[][] dp = new int[str.length() + 1][stables + 1];
        // dp[i][j] -> Cost to accomodate first i horses in j stables.
        if (str.length() < stables)
            return -1;
        // For 1st stable
        for (int i = 1; i <= str.length(); i++)
            dp[i][1] = product(str, 0, i - 1);
        // Considering k stables one by one
        for (int k = 2; k <= stables; k++) {
            // No stable should be empty (that is why j starts from k)
            for (int j = k; j <= str.length(); j++) {
                dp[j][k] = Integer.MAX_VALUE;
                // Now trying different combinations of amount of horses in kth stable
                // putting from ith -> jth horses in kth stables and finding min cost from all
                for (int i = k; i <= j; i++)
                    dp[j][k] = Math.min((dp[i - 1][k - 1] + product(str, i - 1, j - 1)), dp[j][k]);
            }
        }
        return dp[str.length()][stables];
    }
    // This product function call can be replaced by prefix product array
    public int product(String A, int start, int end) {
        int W = 0, B = 0;
        for (int i = start; i <= end; i++) {
            if (A.charAt(i) == 'W')
                W++;
            else if (A.charAt(i) == 'B')
                B++;
        }
        return W * B;
    }
}