Divida una string binaria en K subconjuntos minimizando la suma de productos de ocurrencias de 0 y 1

Dada una string binaria S , la tarea es dividir la secuencia en K subconjuntos no vacíos de modo que la suma de los productos de las ocurrencias de 0 y 1 para todos los subconjuntos sea mínima. Si es imposible imprima -1.
Ejemplos: 
 

Entrada: S = “0001”, K = 2 
Salida: 0 
Explicación 
Tenemos 3 opciones {0, 001}, {00, 01}, {000, 1} 
La suma respectiva de los productos es {1*0 + 2*1 = 2}, {2*0 + 1*1 = 1}, {3*0 + 0*1 = 0}.
Entrada: S = “1011000110110100”, K = 5 
Salida: 8 
Explicación: Los subconjuntos {10, 11, 000, 11011, 0100} minimizan la suma del producto { 1*1 + 0*2 + 3*0 + 1*4 + 3*1 = 8}. 
 

Enfoque: Para resolver este problema estamos usando programación dinámica de abajo hacia arriba . 
 

• Calculamos la suma mínima de productos para todos los subconjuntos y luego, para cada subconjunto usamos este valor para calcular la suma mínima de productos para todos los tamaños de ese subconjunto.
• Para un subconjunto que comience en el índice i y finalice en el índice j , el valor será el mínimo de dp[i-1] + (count_zero * count_one) donde count_zero y count_one son las ocurrencias de 0 y 1 entre i y j respectivamente.
• Para cada índice j , encontramos el valor mínimo entre todos los valores posibles de i .
• Devuelve dp[N – 1] para la respuesta final.

El siguiente código es la implementación del enfoque anterior: 
 

// C++ Program to split a given string
// into K segments such that the sum
// of product of occurrence of
// characters in them is minimized
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// sum of products of occurrences
// of 0 and 1 in each segments
int minSumProd(string S, int K)
{
    // Store the length of
    // the string
    int len = S.length();
 
    // Not possible to
    // generate subsets
    // greater than the
    // length of string
    if (K > len)
        return -1;
 
    // If the number of subsets
    // equals the length
    if (K == len)
        return 0;
 
    vector<int> dp(len);
    int count_zero = 0, count_one = 0;
 
    // Precompute the sum of
    // products for all index
    for (int j = 0; j < len; j++) {
 
        (S[j] == '0')
            ? count_zero++
            : count_one++;
        dp[j] = count_zero * count_one;
    }
 
    // Calculate the minimum sum of
    // products for K subsets
    for (int i = 1; i < K; i++) {
 
        for (int j = len; j >= i; j--) {
 
            count_zero = 0, count_one = 0;
            dp[j] = INT_MAX;
 
            for (int k = j; k >= i; k--) {
 
                (S[k] == '0') ? count_zero++
                              : count_one++;
                dp[j]
                    = min(
                        dp[j],
                        count_zero * count_one
                            + dp[k - 1]);
            }
        }
    }
 
    return dp[len - 1];
}
 
// Driver code
int main()
{
    string S = "1011000110110100";
    int K = 5;
    cout << minSumProd(S, K) << '\n';
    return 0;
}

// Java Program to split a given String
// into K segments such that the sum
// of product of occurrence of
// characters in them is minimized
import java.util.*;
 
class GFG{
 
// Function to return the minimum
// sum of products of occurrences
// of 0 and 1 in each segments
static int minSumProd(String S, int K)
{
    // Store the length of
    // the String
    int len = S.length();
 
    // Not possible to
    // generate subsets
    // greater than the
    // length of String
    if (K > len)
        return -1;
 
    // If the number of subsets
    // equals the length
    if (K == len)
        return 0;
 
    int []dp = new int[len];
    int count_zero = 0, count_one = 0;
 
    // Precompute the sum of
    // products for all index
    for (int j = 0; j < len; j++)
    {
        if(S.charAt(j) == '0')
            count_zero++;
        else
            count_one++;
        dp[j] = count_zero * count_one;
    }
 
    // Calculate the minimum sum of
    // products for K subsets
    for (int i = 1; i < K; i++)
    {
        for (int j = len-1; j >= i; j--)
        {
            count_zero = 0;
            count_one = 0;
            dp[j] = Integer.MAX_VALUE;
 
            for (int k = j; k >= i; k--)
            {
                if(S.charAt(k) == '0')
                    count_zero++;
                else
                    count_one++;
                dp[j] = Math.min(dp[j], count_zero *
                                        count_one +
                                        dp[k - 1]);
            }
        }
    }
     
    return dp[len - 1];
}
 
// Driver code
public static void main(String[] args)
{
    String S = "1011000110110100";
    int K = 5;
    System.out.print(minSumProd(S, K));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to split a given String
# into K segments such that the sum
# of product of occurrence of
# characters in them is minimized
import sys
 
# Function to return the minimum
# sum of products of occurrences
# of 0 and 1 in each segments
def minSumProd(S, K):
     
    # Store the length of
    # the String
    Len = len(S);
 
    # Not possible to
    # generate subsets
    # greater than the
    # length of String
    if (K > Len):
        return -1;
 
    # If the number of subsets
    # equals the length
    if (K == Len):
        return 0;
 
    dp = [0] * Len;
    count_zero = 0;
    count_one = 0;
 
    # Precompute the sum of
    # products for all index
    for j in range(0, Len, 1):
        if (S[j] == '0'):
            count_zero += 1;
        else:
            count_one += 1;
        dp[j] = count_zero * count_one;
 
    # Calculate the minimum sum of
    # products for K subsets
    for i in range(1, K):
        for j in range(Len - 1, i - 1, -1):
            count_zero = 0;
            count_one = 0;
            dp[j] = sys.maxsize;
 
            for k in range(j, i - 1, -1):
                if (S[k] == '0'):
                    count_zero += 1;
                else:
                    count_one += 1;
 
                dp[j] = min(dp[j], count_zero *
                                   count_one +
                                   dp[k - 1]);
    return dp[Len - 1];
 
# Driver code
if __name__ == '__main__':
 
    S = "1011000110110100";
    K = 5;
     
    print(minSumProd(S, K));
 
# This code is contributed by 29AjayKumar

// C# program to split a given String
// into K segments such that the sum
// of product of occurrence of
// characters in them is minimized
using System;
 
class GFG{
 
// Function to return the minimum
// sum of products of occurrences
// of 0 and 1 in each segments
static int minSumProd(string S, int K)
{
     
    // Store the length of
    // the String
    int len = S.Length;
 
    // Not possible to
    // generate subsets
    // greater than the
    // length of String
    if (K > len)
        return -1;
 
    // If the number of subsets
    // equals the length
    if (K == len)
        return 0;
 
    int []dp = new int[len];
    int count_zero = 0, count_one = 0;
 
    // Precompute the sum of
    // products for all index
    for(int j = 0; j < len; j++)
    {
       if(S[j] == '0')
       {
           count_zero++;
       }
       else
       {
           count_one++;
       }
       dp[j] = count_zero * count_one;
    }
 
    // Calculate the minimum sum
    // of products for K subsets
    for(int i = 1; i < K; i++)
    {
       for(int j = len - 1; j >= i; j--)
       {
          count_zero = 0;
          count_one = 0;
          dp[j] = Int32.MaxValue;
           
          for(int k = j; k >= i; k--)
          {
             if(S[k] == '0')
             {
                 count_zero++;
             }
             else
             {
                 count_one++;
             }
             dp[j] = Math.Min(dp[j], count_zero *
                                      count_one +
                                      dp[k - 1]);
          }
       }
    }
    return dp[len - 1];
}
 
// Driver code
public static void Main(string[] args)
{
    string S = "1011000110110100";
    int K = 5;
     
    Console.Write(minSumProd(S, K));
}
}
 
// This code is contributed by rutvik_56

<script>
// Javascript Program to split a given string
// into K segments such that the sum
// of product of occurrence of
// characters in them is minimized
 
 
// Function to return the minimum
// sum of products of occurrences
// of 0 and 1 in each segments
function minSumProd(S, K) {
    // Store the length of
    // the string
    let len = S.length;
 
    // Not possible to
    // generate subsets
    // greater than the
    // length of string
    if (K > len)
        return -1;
 
    // If the number of subsets
    // equals the length
    if (K == len)
        return 0;
 
    let dp = new Array(len);
    let count_zero = 0, count_one = 0;
 
    // Precompute the sum of
    // products for all index
    for (let j = 0; j < len; j++) {
 
        (S[j] == '0')
            ? count_zero++
            : count_one++;
        dp[j] = count_zero * count_one;
    }
 
    // Calculate the minimum sum of
    // products for K subsets
    for (let i = 1; i < K; i++) {
 
        for (let j = len; j >= i; j--) {
 
            count_zero = 0, count_one = 0;
            dp[j] = Number.MAX_SAFE_INTEGER;
 
            for (let k = j; k >= i; k--) {
 
                (S[k] == '0') ? count_zero++
                    : count_one++;
                dp[j]
                    = Math.min(
                        dp[j],
                        count_zero * count_one
                        + dp[k - 1]);
            }
        }
    }
 
    return dp[len - 1];
}
 
// Driver code
let S = "1011000110110100";
let K = 5;
document.write(minSumProd(S, K));
 
// This code is contributed by _saurabh_jaiswal
</script>

8

Complejidad de tiempo: O(K*N*N)  
Complejidad de espacio auxiliar: O(N)