Dada una secuencia binaria de 1 y 0 . Nuestra tarea es eliminar todos los 1 de la secuencia con un costo mínimo mediante las siguientes operaciones.
- Retire un elemento del extremo izquierdo (es decir, elimine s[0]) que cuesta 1 moneda.
- Retire un elemento del extremo derecho (es decir, elimine s[s.length – 1]) que cuesta 1 moneda.
- Elimina un elemento de cualquier parte de la secuencia que cuesta 2 monedas.
Devuelve el costo mínimo para eliminar todos los 1 de la secuencia.
Ejemplos:
Entrada : s = “1100101”
Salida : 5
Explicación :
Quite el “ 1 100101″ más a la izquierda del costo de 1 moneda, nuevo s = “100101”
Quite el “ 1 00101″ más a la izquierda del costo de 1 moneda, nuevo s = “00101”
Quite el “0010 1 ” más a la derecha en el costo de 1 moneda, nuevo s = “0010”
Quite el 1 del medio (“00 1 0″) en el costo de 2 monedas, nuevo s = “000”.
Entonces se requieren un total de 5 monedasEntrada : s = “0010”
Salida : 2
Explicación : Retire el 1 medio (“0010”) por el costo de 2 monedas, nuevo s = “000”
Enfoque : La idea es utilizar DP con ventana deslizante . Use una array dp[N] donde dp[i] almacena la moneda mínima para eliminar todos los 1 del índice i al n-1, donde solo podemos eliminar desde la derecha. Siga los pasos a continuación.
- Bucle desde el índice más a la derecha. Entonces, para cualquier índice i la transición es la siguiente:
- Si es un ‘0’ entonces dp[i]=dp[i+1]
- Si es un ‘1’, entonces tenemos dos opciones: considerar este elemento como uno central y agregar 2 a dp[i+1] o eliminar todos los elementos. Por lo tanto, dp[i]=min(dp[i+1]+2, ni)
- Ahora, también elimine elementos de la izquierda. Entonces, recorre el vector.
- Cuando alcancemos cualquier índice i, consideraremos que hemos eliminado todos los elementos del 0 al i del lado izquierdo.
- Entonces, nuestro tiempo para ese índice será i+1+dp[i+1].
- Dado que hemos eliminado todos los elementos hasta i, solo debemos considerar los elementos de i+1 y, por lo tanto, estamos agregando dp[i+1] a nuestro i+1.
- Finalmente devuelve la respuesta mínima
A continuación se muestra la implementación del código:
C++
// C++ program for find the minimum cost
// to remove all 1's from the given binary string
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum cost
int minimumCoin(string s)
{
int n = s.length();
vector<int> dp(n, 0);
if (s[n - 1] == '0') {
dp[n - 1] = 0;
}
else {
dp[n - 1] = 1;
}
for (int i = n - 2; i >= 0; i--) {
if (s[i] == '0')
dp[i] = dp[i + 1];
if (s[i] == '1') {
// consider current index to
// be a middle one and remove
dp[i] = 2 + dp[i + 1];
// or remove all to the right
dp[i] = min(dp[i], n - i);
}
}
// now go from left to right
int ans = dp[0];
for (int i = 0; i < n - 1; i++) {
// cost of removing all
// from left and dp[i+1]
ans = min(ans, i + 1 + dp[i + 1]);
}
// taking overall minimum
ans = min(ans, n);
return ans;
}
// Driver function
int main()
{
string str = "1001001";
int coins = minimumCoin(str);
cout << coins;
return 0;
}
Java
//Java program for find the minimum cost
// to remove all 1's from the given binary string
import java.io.*;
class GFG {
// Function to find minimum cost
static int minimumCoin(String s)
{
int n = s.length();
int dp[] = new int[n];
if (s.charAt(n - 1) == '0') {
dp[n - 1] = 0;
}
else {
dp[n - 1] = 1;
}
for (int i = n - 2; i >= 0; i--) {
if (s.charAt(i) == '0')
dp[i] = dp[i + 1];
if (s.charAt(i) == '1') {
// consider current index to
// be a middle one and remove
dp[i] = 2 + dp[i + 1];
// or remove all to the right
dp[i] = Math.min(dp[i], n - i);
}
}
// now go from left to right
int ans = dp[0];
for (int i = 0; i < n - 1; i++) {
// cost of removing all
// from left and dp[i+1]
ans = Math.min(ans, i + 1 + dp[i + 1]);
}
// taking overall minimum
ans = Math.min(ans, n);
return ans;
}
// Driver function
public static void main (String[] args) {
String str = "1001001";
int coins = minimumCoin(str);
System.out.println(coins);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the above approach # Function to find minimum cost def minimumCoin(s): n = len(s) dp = [0]*n if (s[n - 1] == '0'): dp[n - 1] = 0 else: dp[n - 1] = 1 for i in range(n-2, -1, -1): if s[i] == '0': dp[i] = dp[i + 1] if s[i] == '1': # consider current index to # be a middle one and remove dp[i] = 2 + dp[i + 1] # or remove all to the right dp[i] = min(dp[i], n - i) # now go from left to right ans = dp[0] for i in range(0, n-1): # cost of removing all # from left and dp[i+1] ans = min(ans, i + 1 + dp[i + 1]) # taking overall minimum ans = min(ans, n) return ans # Driver function str = "1001001" coins = minimumCoin(str) print(coins) # This code is contributed by Potta Lokesh
C#
// C# program for find the minimum cost
// to remove all 1's from the given binary string
using System;
class GFG {
// Function to find minimum cost
static int minimumCoin(string s)
{
int n = s.Length;
int[] dp = new int[n];
if (s[n - 1] == '0') {
dp[n - 1] = 0;
}
else {
dp[n - 1] = 1;
}
for (int i = n - 2; i >= 0; i--) {
if (s[i] == '0')
dp[i] = dp[i + 1];
if (s[i] == '1') {
// consider current index to
// be a middle one and remove
dp[i] = 2 + dp[i + 1];
// or remove all to the right
dp[i] = Math.Min(dp[i], n - i);
}
}
// now go from left to right
int ans = dp[0];
for (int i = 0; i < n - 1; i++) {
// cost of removing all
// from left and dp[i+1]
ans = Math.Min(ans, i + 1 + dp[i + 1]);
}
// taking overall minimum
ans = Math.Min(ans, n);
return ans;
}
// Driver function
public static void Main()
{
string str = "1001001";
int coins = minimumCoin(str);
Console.Write(coins);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for find the minimum cost
// to remove all 1's from the given binary string
// Function to find minimum cost
const minimumCoin = (s) => {
let n = s.length;
let dp = new Array(n).fill(0);
if (s[n - 1] == '0') {
dp[n - 1] = 0;
}
else {
dp[n - 1] = 1;
}
for (let i = n - 2; i >= 0; i--) {
if (s[i] == '0')
dp[i] = dp[i + 1];
if (s[i] == '1') {
// consider current index to
// be a middle one and remove
dp[i] = 2 + dp[i + 1];
// or remove all to the right
dp[i] = Math.min(dp[i], n - i);
}
}
// now go from left to right
let ans = dp[0];
for (let i = 0; i < n - 1; i++) {
// cost of removing all
// from left and dp[i+1]
ans = Math.min(ans, i + 1 + dp[i + 1]);
}
// taking overall minimum
ans = Math.min(ans, n);
return ans;
}
// Driver function
let str = "1001001";
let coins = minimumCoin(str);
document.write(coins);
// This code is contributed by rakeshsahni
</script>
Producción
4
Complejidad temporal: O(n)
Complejidad espacial : O(n)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA