Dadas dos strings X , Y y un entero k . Ahora la tarea es convertir la string X con el costo mínimo tal que la subsecuencia común más larga de X e Y después de la conversión sea de longitud k. El costo de la conversión se calcula como XOR del valor del carácter antiguo y el valor del carácter nuevo. El valor de carácter de ‘a’ es 0, ‘b’ es 1, y así sucesivamente.
Ejemplos:
Input : X = "abble",
Y = "pie",
k = 2
Output : 25
If you changed 'a' to 'z', it will cost 0 XOR 25.
El problema se puede resolver mediante un ligero cambio en el problema de programación dinámica de la subsecuencia creciente más larga . En lugar de dos estados, mantenemos tres estados.
Tenga en cuenta que si k> min (n, m), entonces es imposible alcanzar LCS de al menos k longitud, de lo contrario, siempre es posible.
Deje que dp[i][j][p] almacene el costo mínimo para lograr LCS de longitud p en x[0…i] e y[0….j].
Con paso base como dp[i][j][0] = 0 porque podemos lograr LCS de 0 longitud sin ningún costo y para i < 0 o j 0 en tal caso).
De lo contrario, hay 3 casos:
1. Convertir x[i] en y[j].
2. Omita el i-ésimo carácter de x.
3. Omita j- ésimo carácter de y.
Si convertimos x[i] a y[j], entonces se agregará el costo = f(x[i]) XOR f(y[j]) y LCS disminuirá en 1. f(x) devolverá el valor del carácter de x
Tenga en cuenta que el costo mínimo para convertir un carácter ‘a’ en cualquier carácter ‘c’ es siempre f(a) XOR f(c) porque f(a) XOR f(c) <= (f(a) XOR f(b ) + f(b) XOR f(c)) para todo a, b, c.
Si omite el i- ésimo carácter de x, i se reducirá en 1, no se agregará ningún costo y LCS seguirá siendo el mismo.
Si omite j- ésimo carácter de x, entonces j se reducirá en 1, no se agregará ningún costo y LCS seguirá siendo el mismo.
Por lo tanto,
dp[i][j][k] = min(cost + dp[i - 1][j - 1][k - 1],
dp[i - 1][j][k],
dp[i][j - 1][k])
The minimum cost to make the length of their
LCS atleast k is dp[n - 1][m - 1][k]
C++
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
// Return Minimum cost to make LCS of length k
int solve(char X[], char Y[], int l, int r,
int k, int dp[][N][N])
{
// If k is 0.
if (!k)
return 0;
// If length become less than 0, return
// big number.
if (l < 0 | r < 0)
return 1e9;
// If state already calculated.
if (dp[l][r][k] != -1)
return dp[l][r][k];
// Finding the cost
int cost = (X[l] - 'a') ^ (Y[r] - 'a');
// Finding minimum cost and saving the state value
return dp[l][r][k] = min({cost +
solve(X, Y, l - 1, r - 1, k - 1, dp),
solve(X, Y, l - 1, r, k, dp),
solve(X, Y, l, r - 1, k, dp)});
}
// Driven Program
int main()
{
char X[] = "abble";
char Y[] = "pie";
int n = strlen(X);
int m = strlen(Y);
int k = 2;
int dp[N][N][N];
memset(dp, -1, sizeof dp);
int ans = solve(X, Y, n - 1, m - 1, k, dp);
cout << (ans == 1e9 ? -1 : ans) << endl;
return 0;
}
Java
class GFG
{
static int N = 30;
// Return Minimum cost to make LCS of length k
static int solve(char X[], char Y[], int l, int r,
int k, int dp[][][])
{
// If k is 0.
if (k == 0)
{
return 0;
}
// If length become less than 0, return
// big number.
if (l < 0 | r < 0)
{
return (int) 1e9;
}
// If state already calculated.
if (dp[l][r][k] != -1)
{
return dp[l][r][k];
}
// Finding the cost
int cost = (X[l] - 'a') ^ (Y[r] - 'a');
// Finding minimum cost and saving the state value
return dp[l][r][k] = Math.min(Math.min(cost +
solve(X, Y, l - 1, r - 1, k - 1, dp),
solve(X, Y, l - 1, r, k, dp)),
solve(X, Y, l, r - 1, k, dp));
}
// Driver code
public static void main(String[] args)
{
char X[] = "abble".toCharArray();
char Y[] = "pie".toCharArray();
int n = X.length;
int m = Y.length;
int k = 2;
int[][][] dp = new int[N][N][N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int l = 0; l < N; l++)
{
dp[i][j][l] = -1;
}
}
}
int ans = solve(X, Y, n - 1, m - 1, k, dp);
System.out.println(ans == 1e9 ? -1 : ans);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to calculate Minimum cost
# to make Longest Common Subsequence of length k
N = 30
# Return Minimum cost to make LCS of length k
def solve(X, Y, l, r, k, dp):
# If k is 0
if k == 0:
return 0
# If length become less than 0,
# return big number
if l < 0 or r < 0:
return 1000000000
# If state already calculated
if dp[l][r][k] != -1:
return dp[l][r][k]
# Finding cost
cost = ((ord(X[l]) - ord('a')) ^
(ord(Y[r]) - ord('a')))
dp[l][r][k] = min([cost + solve(X, Y, l - 1,
r - 1, k - 1, dp),
solve(X, Y, l - 1, r, k, dp),
solve(X, Y, l, r - 1, k, dp)])
return dp[l][r][k]
# Driver Code
if __name__ == "__main__":
X = "abble"
Y = "pie"
n = len(X)
m = len(Y)
k = 2
dp = [[[-1] * N for __ in range(N)]
for ___ in range(N)]
ans = solve(X, Y, n - 1, m - 1, k, dp)
print(-1 if ans == 1000000000 else ans)
# This code is contributed
# by vibhu4agarwal
C#
// C# program to find subarray with
// sum closest to 0
using System;
class GFG
{
static int N = 30;
// Return Minimum cost to make LCS of length k
static int solve(char []X, char []Y, int l, int r,
int k, int [,,]dp)
{
// If k is 0.
if (k == 0)
{
return 0;
}
// If length become less than 0, return
// big number.
if (l < 0 | r < 0)
{
return (int) 1e9;
}
// If state already calculated.
if (dp[l,r,k] != -1)
{
return dp[l,r,k];
}
// Finding the cost
int cost = (X[l] - 'a') ^ (Y[r] - 'a');
// Finding minimum cost and saving the state value
return dp[l,r,k] = Math.Min(Math.Min(cost +
solve(X, Y, l - 1, r - 1, k - 1, dp),
solve(X, Y, l - 1, r, k, dp)),
solve(X, Y, l, r - 1, k, dp));
}
// Driver code
public static void Main(String[] args)
{
char []X = "abble".ToCharArray();
char []Y = "pie".ToCharArray();
int n = X.Length;
int m = Y.Length;
int k = 2;
int[,,] dp = new int[N, N, N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int l = 0; l < N; l++)
{
dp[i,j,l] = -1;
}
}
}
int ans = solve(X, Y, n - 1, m - 1, k, dp);
Console.WriteLine(ans == 1e9 ? -1 : ans);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to calculate Minimum cost
// to make Longest Common Subsequence of length k
const N = 30
// Return Minimum cost to make LCS of length k
function solve(X, Y, l, r, k, dp){
// If k is 0
if(k == 0)
return 0
// If length become less than 0,
// return big number
if(l < 0 || r < 0)
return 1000000000
// If state already calculated
if(dp[l][r][k] != -1)
return dp[l][r][k]
// Finding cost
let cost = ((X[l].charCodeAt(0) - 'a'.charCodeAt(0)) ^ (Y[r].charCodeAt(0) - 'a'.charCodeAt(0)))
dp[l][r][k] = Math.min(Math.min(cost + solve(X, Y, l - 1, r - 1, k - 1, dp),solve(X, Y, l - 1, r, k, dp)),
solve(X, Y, l, r - 1, k, dp))
return dp[l][r][k]
}
// Driver Code
let X = "abble"
let Y = "pie"
let n = X.length
let m = Y.length
let k = 2
let dp = new Array(N);
for(let i = 0; i < N; i++)
{
dp[i] = new Array(N);
for(let j = 0; j < N; j++)
{
dp[i][j] = new Array(N).fill(-1);
}
}
let ans = solve(X, Y, n - 1, m - 1, k, dp)
document.write((ans == 1000000000)? -1:ans)
// This code is contributed by shinjanpatra
</script>
Producción:
3