Dadas dos strings A y B de tamaño N y M respectivamente, donde B es una subsecuencia de A y una array arr[] de tamaño N , donde arr[i] es el costo de eliminar el i-ésimo carácter de la string A. La tarea es encontrar el costo mínimo para eliminar caracteres de A de modo que después de la eliminación ninguna subsecuencia de A sea igual a B .
Ejemplos:
Entrada: A = “abccd”, B = “ccd”, arr[] = {1, 2, 3, 4, 5}
Salida: 3
Explicación: si eliminamos la ‘d’ o una sola ‘c’ de A, entonces no será posible construir una subsecuencia igual a B.
Entre estos, el costo de eliminar la ‘c’ en el índice 2 es mínimo, es decir, 3. Entonces, la respuesta es 3.Entrada: A = “abccdabccdabccd”, B = “bccd”, arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
Salida : 21
Explicación: Si quitamos las tres ‘b’ de coste 2, 7 y 5, entonces A se convierte en “accdaccdaccd”.
Ahora no hay forma de construir una subsecuencia = «bccd»
Enfoque: El enfoque ingenuo para resolver el problema es usar la recursividad y encontrar una subsecuencia común entre A y B según la siguiente idea:
Si el carácter de A y B coincide, habrá 2 opciones: eliminar ese carácter de A o mantener ese carácter y eliminar otros caracteres.
Siga los pasos mencionados a continuación para implementar la idea:
- Atraviese recursivamente la string A usando el puntero i y mantenga un puntero j para apuntar a B .
- En cada función recursiva:
- Si se llega al final de la string, devuelve 0 si se elimina algún carácter (verificado por un contador de elementos eliminados); de lo contrario, devuelve un valor positivo alto.
- Si A[i] = B[j] hay dos opciones:
- Elimine A[i] y agregue cost arr[i] para responder y llamar recursivamente a los siguientes elementos.
- Mantén A[i] y avanza.
- De lo contrario, sigue avanzando hasta que A[i] coincida con B[i] .
- Devuelve el costo mínimo entre los dos casos anteriores de cada llamada recursiva.
- Devuelve el costo mínimo como respuesta.
Tiempo Complejidad: O(2 M )
Espacio Auxiliar: O(1)
Enfoque eficiente: el tiempo del enfoque anterior se puede optimizar aún más utilizando la programación dinámica según la siguiente idea:
Use una array 3D dp[][][] para almacenar el costo mínimo hasta una posición determinada en A y B y para eliminar al menos un carácter. dp[i][j][] almacena el costo mínimo para eliminar caracteres hasta el i-ésimo índice de A y el j-ésimo índice de B donde al menos un carácter se elimina o no.
Por lo tanto, la tercera dimensión solo tiene dos valores, ya sea 1 (se elimina al menos uno) o 0 (no se elimina ninguno)
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Array for memoization int dp[101][101][2]; // Recursive function to calculate // the minimum cost using dynamic programming int minCostUtil(string& a, int n, string& b, int m, vector<int>& c, int removed) { // Base case reached the end of string if (n == 0 || m == 0) { // Removed 0 characters // return high (+)ve value if (removed == 0) return 99999; return 0; } // Return pre-calculated value if (dp[n][m][removed > 0 ? 1 : 0] != -1) return dp[n][m][removed > 0 ? 1 : 0]; // If characters match return the minimum of // 1. Removing the character from A and // adding the cost // 2. Moving forward to remove some other // character and decrease the counter as // this character will not be removed. if (a[n - 1] == b[m - 1]) { dp[n][m][removed > 0 ? 1 : 0] = min(c[n - 1] + minCostUtil(a, n - 1, b, m, c, removed), minCostUtil(a, n - 1, b, m - 1, c, removed - 1)); return dp[n][m][removed > 0 ? 1 : 0]; } // If no match then move through string // A and try removing some other // character which matches, i.e can be // part of the subsequence that is equal to B else return dp[n][m][removed > 0 ? 1 : 0] = minCostUtil(a, n - 1, b, m, c, removed); } // Function to calculate minimum cost int minCost(string& a, string& b, vector<int>& c) { memset(dp, -1, sizeof(dp)); return minCostUtil(a, a.size(), b, b.size(), c, b.size()); } // Driver code int main() { string A = "abccdabccdabccd"; string B = "bccd"; vector<int> arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; cout << minCost(A, B, arr); return 0; }
Java
// Java program for the above approach import java.util.*; public class GFG { // Array for memoization static int dp[][][] = new int[101][101][2]; // Recursive function to calculate // the minimum cost using dynamic programming static int minCostUtil(String a, int n, String b, int m, int[] c, int removed) { // Base case reached the end of string if (n == 0 || m == 0) { // Removed 0 characters // return high (+)ve value if (removed == 0) return 99999; return 0; } // Return pre-calculated value if (dp[n][m][removed > 0 ? 1 : 0] != -1) return dp[n][m][removed > 0 ? 1 : 0]; // If characters match return the minimum of // 1. Removing the character from A and // adding the cost // 2. Moving forward to remove some other // character and decrease the counter as // this character will not be removed. if (a.charAt(n - 1) == b.charAt(m - 1)) { dp[n][m][removed > 0 ? 1 : 0] = Math.min(c[n - 1] + minCostUtil(a, n - 1, b, m, c, removed), minCostUtil(a, n - 1, b, m - 1, c, removed - 1)); return dp[n][m][removed > 0 ? 1 : 0]; } // If no match then move through string // A and try removing some other // character which matches, i.e can be // part of the subsequence that is equal to B else return dp[n][m][removed > 0 ? 1 : 0] = minCostUtil(a, n - 1, b, m, c, removed); } // Function to calculate minimum cost static int minCost(String a, String b, int[] c) { for (int i = 0; i < 101; i++) { for (int j = 0; j < 101; j++) { for (int k = 0; k < 2; k++) { dp[i][j][k] = -1; } } } return minCostUtil(a, a.length(), b, b.length(), c, b.length()); } // Driver code public static void main(String args[]) { String A = "abccdabccdabccd"; String B = "bccd"; int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; System.out.print(minCost(A, B, arr)); } } // This code is contributed by Samim Hossain Mondal.
Python3
# Python3 program for the above approach # Array for memoization dp = [] # recursive function to calculate the # minimum cost using dynamic programming def minCostUtil(a, n, b, m, c, removed): global dp # Base Case - reached the end of the string if n == 0 or m == 0: # removed 0 characters # return high +ve value if removed == 0: return 99999 return 0 # return pre - calculated value if dp[n][m][int(bool(removed))] != -1: return dp[n][m][int(bool(removed))] # 1. Removing the character from A and # adding the cost # 2. Moving forward to remove some other # character and decrease the counter as # this character will not be removed. if a[n - 1] == b[m - 1]: dp[n][m][int(bool(removed))] = min(c[n - 1] + minCostUtil(a, n - 1, b, m, c, removed), minCostUtil(a, n - 1, b, m - 1, c, removed - 1)) return dp[n][m][int(bool(removed))] # if no match, then move through string # A and try removing some other # character which matches, ie, can be # part of the subsequence that is equal to B else: dp[n][m][int(bool(removed))] = minCostUtil(a, n - 1, b, m, c, removed) return dp[n][m][int(bool(removed))] # function to calculate minimum bed def minCost(a, b, c): global dp for i in range(101): dp.append([]) for j in range(101): dp[i].append([]) for k in range(2): dp[i][j].append(-1) return minCostUtil(a, len(a), b, len(b), c, len(b)) # Driver Code A = "abccdabccdabccd" B = "bccd" arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] print(minCost(A, B, arr)) # This code is contributed by phasing17
C#
// C# program for the above approach using System; public class GFG{ // Array for memoization static int[,,] dp = new int[101, 101, 2]; // Recursive function to calculate // the minimum cost using dynamic programming static int minCostUtil(string a, int n, string b, int m, int[] c, int removed) { // Base case reached the end of string if (n == 0 || m == 0) { // Removed 0 characters // return high (+)ve value if (removed == 0) return 99999; return 0; } // Return pre-calculated value if (dp[n, m, removed > 0 ? 1 : 0] != -1) return dp[n, m, removed > 0 ? 1 : 0]; // If characters match return the minimum of // 1. Removing the character from A and // adding the cost // 2. Moving forward to remove some other // character and decrease the counter as // this character will not be removed. if (a[n - 1] == b[m - 1]) { dp[n, m, removed > 0 ? 1 : 0] = Math.Min(c[n - 1] + minCostUtil(a, n - 1, b, m, c, removed), minCostUtil(a, n - 1, b, m - 1, c, removed - 1)); return dp[n, m, removed > 0 ? 1 : 0]; } // If no match then move through string // A and try removing some other // character which matches, i.e can be // part of the subsequence that is equal to B else return dp[n, m, removed > 0 ? 1 : 0] = minCostUtil(a, n - 1, b, m, c, removed); } // Function to calculate minimum cost static int minCost(string a, string b, int[] c) { for (int i = 0; i < 101; i++) { for (int j = 0; j < 101; j++) { for (int k = 0; k < 2; k++) { dp[i, j, k] = -1; } } } return minCostUtil(a, a.Length, b, b.Length, c, b.Length); } // Driver code static public void Main (){ string A = "abccdabccdabccd"; string B = "bccd"; int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; Console.Write(minCost(A, B, arr)); } } // This code is contributed by hrithikgarg03188.
Javascript
// JavaScript program for the above approach // Array for memoization var dp = []; // Recursive function to calculate // the minimum cost using dynamic programming function minCostUtil(a, n, b, m, c, removed) { // Base case reached the end of string if (n == 0 || m == 0) { // Removed 0 characters // return high (+)ve value if (removed == 0) return 99999; return 0; } // Return pre-calculated value if (dp[n][m][Number(Boolean(removed))] != -1) return dp[n][m][(removed > 0) ? 1 : 0]; // If characters match return the minimum of // 1. Removing the character from A and // adding the cost // 2. Moving forward to remove some other // character and decrease the counter as // this character will not be removed. if (a[n - 1] == b[m - 1]) { dp[n][m][(removed > 0) ? 1 : 0] = Math.min( c[n - 1] + minCostUtil(a, n - 1, b, m, c, removed), minCostUtil(a, n - 1, b, m - 1, c, removed - 1)); return dp[n][m][(removed > 0) ? 1 : 0]; } // If no match then move through string // A and try removing some other // character which matches, i.e can be // part of the subsequence that is equal to B else return dp[n][m][(removed > 0) ? 1 : 0] = minCostUtil(a, n - 1, b, m, c, removed); } // Function to calculate minimum cost function minCost(a, b, c) { for (var i = 0; i < 101; i++) { dp[i] = []; for (var j = 0; j < 101; j++) { dp[i].push([]); for (var k = 0; k < 2; k++) { dp[i][j].push([-1]); } } } return minCostUtil(a, a.length, b, b.length, c, b.length); } // Driver code var A = "abccdabccdabccd"; var B = "bccd"; var arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ]; document.write(minCost(A, B, arr)); // This code is contributed by phasing17
21
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)