Dada una string binaria S , que consta de 0 y 1. Debe acomodar los 0 y los 1 en los cubos K de tal manera que se cumplan las siguientes condiciones:
- Usted llena los cubos con 0 y 1 conservando el orden relativo de 0 y 1. Por ejemplo, no puede colocar S[1] en el depósito 2 y S[0] en el depósito 1. Debe conservar el orden original de la string binaria.
- Ningún cubo debe dejarse vacío y ningún elemento de la string debe dejarse sin acomodar.
- La suma de todos los productos de (número de 0 * número de 1) para cada cubo debe ser el mínimo entre todos los arreglos de alojamiento posibles.
Si no es posible una solución, imprima -1.
Ejemplos:
Input: S = "0001", K = 2
Output: 0
We have 3 choices {"0", "001"}, {"00", "01"}, {"000", 1}
First choice, we will get 1*0 + 2*1 = 2
Second choice, we will get 2*0 + 1*1 = 1
Third choice, we will get 3*0 + 0*1 = 0
Out of all the 3 choices, the third choice
is giving the minimum answer.
Input: S = "0101", K = 1
Output: 1
Implementación recursiva: debe acomodar la string binaria en K cubos sin alterar las condiciones anteriores. Luego, se puede hacer una solución recursiva simple llenando primero el cubo i-th (comenzando desde 0) colocando elementos desde el inicio hasta N (N = longitud de la string binaria) y seguir agregando ceros y unos hasta el índice de inicio. Para cada iteración, si hay x ceros e y unos hasta el inicio, recurra para f(inicio, K) = x * y + f(inicio + 1, K – 1) porque la siguiente acomodación se realizará desde (inicio + 1)- El índice y los cubos restantes serán K – 1.
Entonces, la fórmula recursiva será:
F(start, current_bucket) = | |
| min | F(i + 1, next_bucket) + (ones * zeroes in current_bucket)
| |
| i = start to N
Enfoque dinámico de arriba hacia abajo:
la relación recursiva se puede cambiar a solución dinámica guardando los resultados de diferentes combinaciones de variables de inicio y cubo en una array DP 2-D. Podemos usar el hecho de que se debe conservar el orden de la string. Puede tener una array 2-D guardando los estados de tamaño [tamaño de la string * cubos] , donde dp[i][j] nos dirá el valor mínimo de alojamiento hasta el i-ésimo índice de la string usando j + 1 cubos. Nuestra respuesta final estará en dp[N-1][K-1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// 2-D dp array saving different states
// dp[i][j] = minimum value of accommodation
// till i'th index of the string
// using j+1 number of buckets.
vector<vector<int> > dp;
// Function to find the minimum required
// sum using dynamic programming
int solveUtil(int start, int bucket, string str, int K)
{
int N = str.size();
// If both start and bucket reached end then
// return 0 else that arrangement is not possible
// so return INT_MAX
if (start == N) {
if (bucket == K)
return 0;
return INT_MAX;
}
// Corner case
if (bucket == K)
return INT_MAX;
// If state if already calculated
// then return its answer
if (dp[start][bucket] != -1)
return dp[start][bucket];
int zeroes = 0;
int ones = 0;
int ans = INT_MAX;
// Start filling zeroes and ones which to be accommodated
// in jth bucket then ans for current arrangement will be
// ones*zeroes + recur(i+1, bucket+1)
for (int i = start; i < N; ++i) {
if (str[i] == '1')
ones++;
else
zeroes++;
if (ones * zeroes > ans)
break;
int temp = solveUtil(i + 1, bucket + 1, str, K);
// If this arrangement is not possible then
// don't calculate further
if (temp != INT_MAX) {
ans = min(ans, temp + (ones * zeroes));
}
}
return dp[start][bucket] = ans;
}
// Function to initialize the dp and call
// solveUtil() method to get the answer
int solve(string str, int K)
{
int N = str.size();
dp.clear();
dp.resize(N, vector<int>(K, -1));
// Start with 0-th index and 1 bucket
int ans = solveUtil(0, 0, str, K);
return ans == INT_MAX ? -1 : ans;
}
// Driver code
int main()
{
string S = "0101";
// K buckets
int K = 2;
cout << solve(S, K) << endl;
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG{
// 2-D dp array saving different states
// dp[i][j] = minimum value of accommodation
// till i'th index of the string
// using j+1 number of buckets.
static int[][] dp;
// Function to find the minimum required
// sum using dynamic programming
static int solveUtil(int start, int bucket,
String str, int K)
{
int N = str.length();
// If both start and bucket reached end
// then return 0 else that arrangement
// is not possible so return INT_MAX
if (start == N)
{
if (bucket == K)
{
return 0;
}
return Integer.MAX_VALUE;
}
// Corner case
if (bucket == K)
{
return Integer.MAX_VALUE;
}
// If state if already calculated
// then return its answer
if (dp[start][bucket] != -1)
{
return dp[start][bucket];
}
int zeroes = 0;
int ones = 0;
int ans = Integer.MAX_VALUE;
// Start filling zeroes and ones which to be
// accommodated in jth bucket then ans for
// current arrangement will be
// ones*zeroes + recur(i+1, bucket+1)
for(int i = start; i < N; ++i)
{
if (str.charAt(i) == '1')
{
ones++;
}
else
{
zeroes++;
}
if (ones * zeroes > ans)
{
break;
}
int temp = solveUtil(i + 1, bucket + 1, str, K);
// If this arrangement is not possible then
// don't calculate further
if (temp != Integer.MAX_VALUE)
{
ans = Math.min(ans, temp + (ones * zeroes));
}
}
return dp[start][bucket] = ans;
}
// Function to initialize the dp and call
// solveUtil() method to get the answer
static int solve(String str, int K)
{
int N = str.length();
dp = new int[N][K];
for(int[] row : dp)
{
Arrays.fill(row, -1);
}
// Start with 0-th index and 1 bucket
int ans = solveUtil(0, 0, str, K);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// Driver code
public static void main(String[] args)
{
String S = "0101";
// K buckets
int K = 2;
System.out.println(solve(S, K));
}
}
// This code is contributed by rag2127
Python3
# Python3 implementation of the approach # 2-D dp array saving different states # dp[i][j] = minimum value of accommodation # till i'th index of the string # using j+1 number of buckets. # Function to find the minimum required # sum using dynamic programming def solveUtil(start, bucket, str1, K,dp): N = len(str1) # If both start and bucket reached end then # return 0 else that arrangement is not possible # so return INT_MAX if (start == N) : if (bucket == K): return 0 return 10**9 # Corner case if (bucket == K): return 10**9 # If state if already calculated # then return its answer if (dp[start][bucket] != -1): return dp[start][bucket] zeroes = 0 ones = 0 ans = 10**9 # Start filling zeroes and ones which to be accommodated # in jth bucket then ans for current arrangement will be # ones*zeroes + recur(i+1, bucket+1) for i in range(start,N): if (str1[i] == '1'): ones += 1 else: zeroes += 1 if (ones * zeroes > ans): break temp = solveUtil(i + 1, bucket + 1, str1, K,dp) # If this arrangement is not possible then # don't calculate further if (temp != 10**9): ans = min(ans, temp + (ones * zeroes)) dp[start][bucket] = ans return ans # Function to initialize the dp and call # solveUtil() method to get the answer def solve(str1, K): N = len(str1) dp = [[-1 for i in range(K)] for i in range(N)] # Start with 0-th index and 1 bucket ans = solveUtil(0, 0, str1, K,dp) if ans == 10**9: return -1 else: return ans # Driver code s = "0101" S=[i for i in s] # K buckets K = 2 print(solve(S, K)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// 2-D dp array saving different states
// dp[i][j] = minimum value of accommodation
// till i'th index of the string
// using j+1 number of buckets.
static int[,] dp;
// Function to find the minimum required
// sum using dynamic programming
static int solveUtil(int start, int bucket,
string str, int K)
{
int N = str.Length;
// If both start and bucket reached end
// then return 0 else that arrangement
// is not possible so return INT_MAX
if (start == N)
{
if (bucket == K)
{
return 0;
}
return Int32.MaxValue;
}
// Corner case
if (bucket == K)
{
return Int32.MaxValue;
}
// If state if already calculated
// then return its answer
if (dp[start,bucket] != -1)
{
return dp[start, bucket];
}
int zeroes = 0;
int ones = 0;
int ans = Int32.MaxValue;
// Start filling zeroes and ones which to be
// accommodated in jth bucket then ans for
// current arrangement will be
// ones*zeroes + recur(i+1, bucket+1)
for(int i = start; i < N; ++i)
{
if (str[i] == '1')
{
ones++;
}
else
{
zeroes++;
}
if (ones * zeroes > ans)
{
break;
}
int temp = solveUtil(i + 1, bucket + 1, str, K);
// If this arrangement is not possible then
// don't calculate further
if (temp != Int32.MaxValue)
{
ans = Math.Min(ans, temp + (ones * zeroes));
}
}
return dp[start, bucket] = ans;
}
// Function to initialize the dp and call
// solveUtil() method to get the answer
static int solve(string str, int K)
{
int N = str.Length;
dp = new int[N, K];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < K; j++)
{
dp[i, j] = -1;
}
}
// Start with 0-th index and 1 bucket
int ans = solveUtil(0, 0, str, K);
return ans == Int32.MaxValue ? -1 : ans;
}
// Driver code
static void Main()
{
string S = "0101";
// K buckets
int K = 2;
Console.WriteLine(solve(S, K));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation of the approach
// 2-D dp array saving different states
// dp[i][j] = minimum value of accommodation
// till i'th index of the string
// using j+1 number of buckets.
let dp;
// Function to find the minimum required
// sum using dynamic programming
function solveUtil(start, bucket, str, K)
{
let N = str.length;
// If both start and bucket reached end
// then return 0 else that arrangement
// is not possible so return INT_MAX
if (start == N)
{
if (bucket == K)
{
return 0;
}
return Number.MAX_VALUE;
}
// Corner case
if (bucket == K)
{
return Number.MAX_VALUE;
}
// If state if already calculated
// then return its answer
if (dp[start][bucket] != -1)
{
return dp[start][bucket];
}
let zeroes = 0;
let ones = 0;
let ans = Number.MAX_VALUE;
// Start filling zeroes and ones which to be
// accommodated in jth bucket then ans for
// current arrangement will be
// ones*zeroes + recur(i+1, bucket+1)
for(let i = start; i < N; ++i)
{
if (str[i] == '1')
{
ones++;
}
else
{
zeroes++;
}
if (ones * zeroes > ans)
{
break;
}
let temp = solveUtil(i + 1, bucket + 1, str, K);
// If this arrangement is not possible then
// don't calculate further
if (temp != Number.MAX_VALUE)
{
ans = Math.min(ans, temp + (ones * zeroes));
}
}
return dp[start][bucket] = ans;
}
// Function to initialize the dp and call
// solveUtil() method to get the answer
function solve(str, K)
{
let N = str.length;
dp = new Array(N);
for(let i = 0; i < N; i++)
{
dp[i] = new Array(K);
for(let j = 0; j < K; j++)
{
dp[i][j] = -1;
}
}
// Start with 0-th index and 1 bucket
let ans = solveUtil(0, 0, str, K);
return ans == Number.MAX_VALUE ? -1 : ans;
}
// Driver code
let S = "0101";
// K buckets
let K = 2;
document.write(solve(S, K));
// This code is contributed by unknown2108
</script>
Producción:
2
Complejidad Temporal: O(N 3 )
Complejidad Espacial: O(N 2 )
Esta solución aún no está optimizada porque llama al mismo estado varias veces. Entonces, ahora analice el enfoque optimizado de DP de abajo hacia arriba.
Enfoque dinámico ascendente: Tratemos de pensar primero en el estado final. Aquí las variables son el número de cubos y el índice de la string. Sea dp[i][j] la suma mínima de productos para los elementos de string 0 a j-1 y i cubos. Ahora, para definir nuestra función de transición, tendremos que comenzar desde atrás y considerar la partición en cada posición k posible. Por lo tanto, nuestra función de transición se ve así:
dp [i][j] = for all k = 0 to j min(dp[i][k-1] + numberOfZeroes * numberOfOnes) for i = 0 (single partition) simple count number of 0's and 1's and do the multiplication. And if number of buckets is more than string length till now ans is -1 as we cant fill all the available buckets.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum required
// sum using dynamic programming
int solve(string str, int K)
{
int n = str.length();
// dp[i][j] = minimum val of accommodation
// till j'th index of the string
// using i+1 number of buckets.
// Final ans will be in dp[n-1][K-1]
long long dp[K][n];
// Initialise dp with all states as 0
memset(dp, 0, sizeof dp);
// Corner cases
if (n < K)
return -1;
else if (n == K)
return 0;
// Filling first row, if only 1 bucket then simple count
// number of zeros and ones and do the multiplication
long long zeroes = 0, ones = 0;
for (int i = 0; i < n; i++) {
if (str[i] == '0')
zeroes++;
else
ones++;
dp[0][i] = ones * zeroes;
}
for (int s = 1; s < K; s++) {
for (int i = 0; i < n; i++) {
dp[s][i] = INT_MAX;
ones = 0;
zeroes = 0;
for (int k = i; k >= 0; k--) {
if (str[k] == '0')
zeroes++;
else
ones++;
// If k = 0 then this arrangement is not possible
dp[s][i] = min(dp[s][i],
+((k - 1 >= 0)
? ones * zeroes + dp[s - 1][k - 1]
: INT_MAX));
}
}
}
// If no arrangement is possible then
// our answer will remain INT_MAX so return -1
return (dp[K - 1][n - 1] == INT_MAX) ? -1 : dp[K - 1][n - 1];
}
// Driver code
int main()
{
string S = "0101";
// K buckets
int K = 2;
cout << solve(S, K) << endl;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to find the minimum required
// sum using dynamic programming
static long solve(String str, int K)
{
int n = str.length();
// dp[i][j] = minimum val of accommodation
// till j'th index of the string
// using i+1 number of buckets.
// Final ans will be in dp[n-1][K-1]
long dp[][] = new long[K][n];
// Corner cases
if (n < K)
return -1;
else if (n == K)
return 0;
// Filling first row, if only 1 bucket then simple count
// number of zeros and ones and do the multiplication
long zeroes = 0, ones = 0;
for (int i = 0; i < n; i++)
{
if (str.charAt(i) == '0')
zeroes++;
else
ones++;
dp[0][i] = ones * zeroes;
}
for (int s = 1; s < K; s++)
{
for (int i = 0; i < n; i++)
{
dp[s][i] = Integer.MAX_VALUE;
ones = 0;
zeroes = 0;
for (int k = i; k >= 0; k--)
{
if (str.charAt(k) == '0')
zeroes++;
else
ones++;
// If k = 0 then this arrangement is not possible
dp[s][i] = Math.min(dp[s][i],
+((k - 1 >= 0)
? ones * zeroes + dp[s - 1][k - 1]
: Integer.MAX_VALUE));
}
}
}
// If no arrangement is possible then
// our answer will remain INT_MAX so return -1
return (dp[K - 1][n - 1] == Integer.MAX_VALUE) ? -1 : dp[K - 1][n - 1];
}
// Driver code
public static void main (String[] args)
{
String S = "0101";
// K buckets
int K = 2;
System.out.println(solve(S, K));
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the approach import sys # Function to find the minimum required # sum using dynamic programming def solve(Str, K): n = len(Str) # dp[i][j] = minimum val of accommodation # till j'th index of the string # using i+1 number of buckets. # Final ans will be in dp[n-1][K-1] # Initialise dp with all states as 0 dp = [[0 for i in range(n)] for j in range(K)] # Corner cases if(n < K): return -1 elif(n == K): return 0 # Filling first row, if only 1 bucket then simple count # number of zeros and ones and do the multiplication zeroes = 0 ones = 0 for i in range(n): if(Str[i] == '0'): zeroes += 1 else: ones += 1 dp[0][i] = ones * zeroes for s in range(1, K): for i in range(n): dp[s][i] = sys.maxsize ones = 0 zeroes = 0 for k in range(i, -1, -1): if(Str[k] == '0'): zeroes += 1 else: ones += 1 # If k = 0 then this arrangement # is not possible temp = 0 if(k - 1 >= 0): temp = ones * zeroes + dp[s - 1][k - 1] else: temp = sys.maxsize dp[s][i] = min(dp[s][i], temp) # If no arrangement is possible then # our answer will remain INT_MAX so return -1 if(dp[K - 1][n - 1] == sys.maxsize): return -1 else: return dp[K - 1][n - 1] # Driver code S = "0101" # K buckets K = 2 print(solve(S, K)) # This code is contributed by avanitrachhadiya2155
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find the minimum required
// sum using dynamic programming
static long solve(string str, int K)
{
int n = str.Length;
// dp[i, j] = minimum val of accommodation
// till j'th index of the string
// using i+1 number of buckets.
// Final ans will be in dp[n-1, K-1]
long [, ] dp = new long[K, n];
// Corner cases
if (n < K)
return -1;
else if (n == K)
return 0;
// Filling first row, if only 1 bucket then simple count
// number of zeros and ones and do the multiplication
long zeroes = 0, ones = 0;
for (int i = 0; i < n; i++)
{
if (str[i] == '0')
zeroes++;
else
ones++;
dp[0, i] = ones * zeroes;
}
for (int s = 1; s < K; s++)
{
for (int i = 0; i < n; i++)
{
dp[s, i] = Int32.MaxValue;
ones = 0;
zeroes = 0;
for (int k = i; k >= 0; k--)
{
if (str[k] == '0')
zeroes++;
else
ones++;
// If k = 0 then this arrangement is not possible
dp[s, i] = Math.Min(dp[s, i],
+((k - 1 >= 0)
? ones * zeroes + dp[s - 1, k - 1]
: Int32.MaxValue));
}
}
}
// If no arrangement is possible then
// our answer will remain INT_MAX so return -1
return (dp[K - 1, n - 1] == Int32.MaxValue) ? -1 : dp[K - 1, n - 1];
}
// Driver code
public static void Main (string[] args)
{
string S = "0101";
// K buckets
int K = 2;
Console.WriteLine(solve(S, K));
}
}
// This code is contributed by ihritik
Javascript
<script>
// JavaScript implementation of the approach
// Function to find the minimum required
// sum using dynamic programming
function solve(str,K)
{
let n = str.length;
// dp[i][j] = minimum val of accommodation
// till j'th index of the string
// using i+1 number of buckets.
// Final ans will be in dp[n-1][K-1]
let dp = new Array(K);
for(let i=0;i<K;i++)
{
dp[i]=new Array(n);
for(let j=0;j<n;j++)
{
dp[i][j]=0;
}
}
// Corner cases
if (n < K)
return -1;
else if (n == K)
return 0;
// Filling first row, if only 1 bucket then simple count
// number of zeros and ones and do the multiplication
let zeroes = 0, ones = 0;
for (let i = 0; i < n; i++)
{
if (str[i] == '0')
zeroes++;
else
ones++;
dp[0][i] = ones * zeroes;
}
for (let s = 1; s < K; s++)
{
for (let i = 0; i < n; i++)
{
dp[s][i] = Number.MAX_VALUE;
ones = 0;
zeroes = 0;
for (let k = i; k >= 0; k--)
{
if (str[k] == '0')
zeroes++;
else
ones++;
// If k = 0 then this
// arrangement is not possible
dp[s][i] = Math.min(dp[s][i],
+((k - 1 >= 0)
? ones * zeroes + dp[s - 1][k - 1]
: Number.MAX_VALUE));
}
}
}
// If no arrangement is possible then
// our answer will remain INT_MAX so return -1
return (dp[K - 1][n - 1] == Number.MAX_VALUE) ?
-1 : dp[K - 1][n - 1];
}
// Driver code
let S = "0101";
// K buckets
let K = 2;
document.write(solve(S, K));
// This code is contributed by patel2127
</script>
Producción:
2
Complejidad Temporal: O(N 3 )
Complejidad Espacial: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por tyagikartik4282 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA