Una string se denomina string de N copias cuando está formada por N copias de la letra ‘G’. es decir, “GGGG” es una string de 4 copias ya que contiene 4 copias de la letra ‘G’. Inicialmente tenemos una string vacía en la que podemos realizar las siguientes tres operaciones:
- Agregue una sola letra ‘G’ con un costo de X.
- Eliminar una sola letra ‘G’ con un costo de X.
- Agregue la string formada hasta ahora a sí misma con un costo de Y, es decir, tenemos la string ‘GG’, podemos agregarla a sí misma para hacer ‘GGGG’
Dado N, X e Y, encuentre el costo mínimo para generar la string N-copia utilizando las operaciones anteriores
Ejemplos:
Entrada: N = 4, X = 2, Y = 1
Salida: 4
Explicación:
1) Inicialmente, la string está vacía, realizamos una operación Agregar para formar la string ‘G’.
2) A continuación, realizamos una operación de tipo 3 y formamos la string ‘GG’.
3) Nuevamente realizamos la operación 3 y formamos ‘GGGG’, que es la string de copias N requerida.
Costo = X + Y + Y = 2 + 1 + 1 = 4
Entrada: N = 4, X = 1, Y = 3
Salida: 4
Podemos realizar 4 operaciones de suma consecutivas para formar ‘GGGG’.
Costo = X + X + X + X = 1 + 1 + 1 + 1 = 4
El problema se puede resolver utilizando un enfoque de programación dinámica.
Si analizamos cuidadosamente las operaciones, es fácil ver que realizamos la operación de eliminación solo cuando hay una copia adicional a la requerida, esto solo puede ser el caso cuando antes de esta operación de eliminación había una operación de tipo 3 involucrada, porque si hubo una operación de tipo 1 antes, entonces no tiene sentido ya que las operaciones consecutivas de agregar y quitar solo aumentan el costo, sin introducir nuevas copias en nuestra string.
Por lo tanto, podemos decir que tenemos las siguientes operaciones:
1) Agregar un solo carácter ‘G’, con costo X
2) Agregar la string a sí mismo y luego eliminar un solo carácter ‘G’, con costo Y + X
3) Agregar la string a sí mismo, con costo Y
Nota: A continuación nos referimos a estas operaciones modificadas.
Ahora, se puede resolver con un enfoque O(n) DP.
Si dp[i] representa el costo mínimo para formar una string de copia i
, entonces las transiciones de estado pueden ser:
1) Si i es impar,
Caso 1: Agregue un carácter a la string de copia (i-1) ,
Caso 2: Realice una operación de tipo 2 en la string de copia ((i+1)/2),
es decir, dp[i] = min(dp[i – 1] + X, dp[(i + 1) / 2)] + Y + X)
2) Si i es par
Caso 1: Agregue un carácter a la string de copia (i-1) ,
Caso 2: Realice una operación de tipo 3 en la string de copia (i/2)
, es decir, dp[i] = min(dp[i – 1] + X, dp[i / 2] + Y)
C++
// CPP code to find minimum cost to form a
// N-copy string
#include <bits/stdc++.h>
using namespace std;
// Returns the minimum cost to form a n-copy string
// Here, x -> Cost to add/remove a single character 'G'
// and y-> cost to append the string to itself
int findMinimumCost(int n, int x, int y)
{
int* dp = new int[n + 1];
// Base Case: to form a 1-copy string we
// need to perform an operation of type
// 1(i.e Add)
dp[1] = x;
for (int i = 2; i <= n; i++) {
if (i & 1) {
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 2 operation
// on ((i + 1) / 2)-copy string
dp[i] = min(dp[i - 1] + x, dp[(i + 1) / 2] + y + x);
}
else {
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 3 operation on
// (i/2)-copy string
dp[i] = min(dp[i - 1] + x, dp[i / 2] + y);
}
}
return dp[n];
}
// Driver Code
int main()
{
int n = 4, x = 2, y = 1;
cout << findMinimumCost(n, x, y);
return 0;
}
Java
// Java code to find minimum cost to form a
// N-copy string
class Solution
{
// Returns the minimum cost to form a n-copy string
// Here, x -> Cost to add/remove a single character 'G'
// and y-> cost to append the string to itself
static int findMinimumCost(int n, int x, int y)
{
int dp[] = new int[n + 1];
// Base Case: to form a 1-copy string we
// need to perform an operation of type
// 1(i.e Add)
dp[1] = x;
for (int i = 2; i <= n; i++) {
if ((i & 1)!=0) {
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 2 operation
// on ((i + 1) / 2)-copy string
dp[i] = Math.min(dp[i - 1] + x, dp[(i + 1) / 2] + y + x);
}
else {
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 3 operation on
// (i/2)-copy string
dp[i] = Math.min(dp[i - 1] + x, dp[i / 2] + y);
}
}
return dp[n];
}
// Driver Code
public static void main(String args[])
{
int n = 4, x = 2, y = 1;
System.out.println( findMinimumCost(n, x, y));
}
}
//contributed by Arnab Kundu
Python3
# Python3 code to find minimum cost to # form a N-copy string # function returns the minimum cost to # form a n-copy string Here, x->Cost to # add/remove a single character 'G' and # y->cost to append the string to itself def findMinimumCost(n, x, y): dp = [0 for i in range(n + 1)] # base case: ro form a 1-copy string # we need tp perform an operation # of type 1(i,e Add) dp[1] = x for i in range(2, n + 1): if i & 1: # case1. Perform a Add operation # on (i-1)copy string # case2. perform a type 2 operation # on((i+1)/2)-copy string dp[i] = min(dp[i - 1] + x, dp[(i + 1) // 2] + y + x) else: # case1. Perform a Add operation # on (i-1)-copy string # case2. Perform a type # operation # on (i/2)-copy string dp[i] = min(dp[i - 1] + x, dp[i // 2] + y) return dp[n] # Driver code n, x, y = 4, 2, 1 print(findMinimumCost(n, x, y)) # This code is contributed # by Mohit Kumar
C#
// C# code to find minimum cost to form a
// N-copy string
using System;
class GFG
{
// Returns the minimum cost to form a n-copy string
// Here, x -> Cost to add/remove a single character 'G'
// and y-> cost to append the string to itself
static int findMinimumCost(int n, int x, int y)
{
int[] dp = new int[n + 1];
// Base Case: to form a 1-copy string we
// need to perform an operation of type
// 1(i.e Add)
dp[1] = x;
for (int i = 2; i <= n; i++)
{
if ((i & 1)!=0)
{
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 2 operation
// on ((i + 1) / 2)-copy string
dp[i] = Math.Min(dp[i - 1] + x,
dp[(i + 1) / 2] + y + x);
}
else
{
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 3 operation on
// (i/2)-copy string
dp[i] = Math.Min(dp[i - 1] + x,
dp[i / 2] + y);
}
}
return dp[n];
}
// Driver Code
public static void Main()
{
int n = 4, x = 2, y = 1;
Console.WriteLine(findMinimumCost(n, x, y));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP code to find minimum cost to form a
// N-copy string
// Returns the minimum cost to form a n-copy
// string. Here, x -> Cost to add/remove a
// single character 'G' and y-> cost to
// append the string to itself
function findMinimumCost($n, $x, $y)
{
$dp[$n + 1] = array();
// Base Case: to form a 1-copy string
// we need to perform an operation of
// type 1(i.e Add)
$dp[1] = $x;
for ($i = 2; $i <= $n; $i++)
{
if ($i & 1)
{
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 2 operation
// on ((i + 1) / 2)-copy string
$dp[$i] = min($dp[$i - 1] + $x,
$dp[($i + 1) / 2] + $y + $x);
}
else
{
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 3 operation on
// (i/2)-copy string
$dp[$i] = min($dp[$i - 1] + $x,
$dp[$i / 2] + $y);
}
}
return $dp[$n];
}
// Driver Code
$n = 4;
$x = 2;
$y = 1;
echo findMinimumCost($n, $x, $y);
// This code is contributed by Sach_Code
?>
Javascript
<script>
// Javascript code to find minimum cost to form a
// N-copy string
// Returns the minimum cost to form a n-copy string
// Here, x -> Cost to add/remove a single character 'G'
// and y-> cost to append the string to itself
function findMinimumCost(n, x, y)
{
let dp = new Array(n + 1);
// Base Case: to form a 1-copy string we
// need to perform an operation of type
// 1(i.e Add)
dp[1] = x;
for (let i = 2; i <= n; i++) {
if ((i & 1)!=0) {
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 2 operation
// on ((i + 1) / 2)-copy string
dp[i] = Math.min(dp[i - 1] + x, dp[parseInt((i + 1) / 2, 10)] + y + x);
}
else {
// Case1. Perform a Add operation on
// (i-1)-copy string,
// Case2. Perform a type 3 operation on
// (i/2)-copy string
dp[i] = Math.min(dp[i - 1] + x, dp[parseInt(i / 2, 10)] + y);
}
}
return dp[n];
}
let n = 4, x = 2, y = 1;
document.write(findMinimumCost(n, x, y));
</script>
Producción:
4
Tiempo Complejidad O(n)
Espacio Auxiliar O(n)