Dadas dos secuencias P y Q de números. La tarea es encontrar la subsecuencia común más larga de dos secuencias si se nos permite cambiar como máximo el elemento k en la primera secuencia a cualquier valor.
Ejemplos:
Input : P = { 8, 3 }
Q = { 1, 3 }
K = 1
Output : 2
If we change first element of first
sequence from 8 to 1, both sequences
become same.
Input : P = { 1, 2, 3, 4, 5 }
Q = { 5, 3, 1, 4, 2 }
K = 1
Output : 3
By changing first element of first
sequence to 5 to get the LCS ( 5, 3, 4 }.
La idea es usar Programación Dinámica. Defina una array 3D dp[][][], donde dp[i][j][k] define la subsecuencia común más larga para los primeros números i de la primera array, el primer número j de la segunda array cuando se nos permite cambiar en max k número en la primera array.
Por lo tanto, la recursión se verá como
If P[i] != Q[j],
dp[i][j][k] = max(dp[i - 1][j][k],
dp[i][j - 1][k],
dp[i - 1][j - 1][k - 1] + 1)
If P[i] == Q[j],
dp[i][j][k] = max(dp[i - 1][j][k],
dp[i][j - 1][k],
dp[i - 1][j - 1][k] + 1)
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to find LCS of two arrays with
// k changes allowed in first array.
#include <bits/stdc++.h>
using namespace std;
#define MAX 10
// Return LCS with at most k changes allowed.
int lcs(int dp[MAX][MAX][MAX], int arr1[], int n,
int arr2[], int m, int k)
{
// If at most changes is less than 0.
if (k < 0)
return -1e7;
// If any of two array is over.
if (n < 0 || m < 0)
return 0;
// Making a reference variable to dp[n][m][k]
int& ans = dp[n][m][k];
// If value is already calculated, return
// that value.
if (ans != -1)
return ans;
// calculating LCS with no changes made.
ans = max(lcs(dp, arr1, n - 1, arr2, m, k),
lcs(dp, arr1, n, arr2, m - 1, k));
// calculating LCS when array element are same.
if (arr1[n-1] == arr2[m-1])
ans = max(ans, 1 + lcs(dp, arr1, n - 1,
arr2, m - 1, k));
// calculating LCS with changes made.
ans = max(ans, 1 + lcs(dp, arr1, n - 1,
arr2, m - 1, k - 1));
return ans;
}
// Driven Program
int main()
{
int k = 1;
int arr1[] = { 1, 2, 3, 4, 5 };
int arr2[] = { 5, 3, 1, 4, 2 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int m = sizeof(arr2) / sizeof(arr2[0]);
int dp[MAX][MAX][MAX];
memset(dp, -1, sizeof(dp));
cout << lcs(dp, arr1, n, arr2, m, k) << endl;
return 0;
}
Java
// Java program to find LCS of two arrays with
// k changes allowed in first array.
class GFG
{
static int MAX = 10;
// Return LCS with at most k changes allowed.
static int lcs(int[][][] dp, int[] arr1,
int n, int[] arr2, int m, int k)
{
// If at most changes is less than 0.
if (k < 0)
return -10000000;
// If any of two array is over.
if (n < 0 || m < 0)
return 0;
// Making a reference variable to dp[n][m][k]
int ans = dp[n][m][k];
// If value is already calculated, return
// that value.
if (ans != -1)
return ans;
try
{
// calculating LCS with no changes made.
ans = Math.max(lcs(dp, arr1, n - 1, arr2, m, k),
lcs(dp, arr1, n, arr2, m - 1, k));
// calculating LCS when array element are same.
if (arr1[n - 1] == arr2[m - 1])
ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1,
arr2, m - 1, k));
// calculating LCS with changes made.
ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1,
arr2, m - 1, k - 1));
} catch (Exception e) { }
// Storing the value in dp.
dp[n][m][k] = ans;
return ans;
}
// Driver Code
public static void main(String[] args)
{
int k = 1;
int[] arr1 = { 1, 2, 3, 4, 5 };
int[] arr2 = { 5, 3, 1, 4, 2 };
int n = arr1.length;
int m = arr2.length;
int[][][] dp = new int[MAX][MAX][MAX];
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
for (int l = 0; l < MAX; l++)
dp[i][j][l] = -1;
System.out.println(lcs(dp, arr1, n, arr2, m, k));
}
}
// This code is contributed by
// krishnat208026
Python3
# Python3 program to find LCS of two arrays # with k changes allowed in the first array. MAX = 10 # Return LCS with at most k changes allowed. def lcs(dp, arr1, n, arr2, m, k): # If at most changes is less than 0. if k < 0: return -(10 ** 7) # If any of two array is over. if n < 0 or m < 0: return 0 # Making a reference variable to dp[n][m][k] ans = dp[n][m][k] # If value is already calculated, # return that value. if ans != -1: return ans # calculating LCS with no changes made. ans = max(lcs(dp, arr1, n - 1, arr2, m, k), lcs(dp, arr1, n, arr2, m - 1, k)) # calculating LCS when array element are same. if arr1[n-1] == arr2[m-1]: ans = max(ans, 1 + lcs(dp, arr1, n - 1, arr2, m - 1, k)) # calculating LCS with changes made. ans = max(ans, lcs(dp, arr1, n - 1, arr2, m - 1, k - 1)) return ans # Driven Program if __name__ == "__main__": k = 1 arr1 = [1, 2, 3, 4, 5] arr2 = [5, 3, 1, 4, 2] n = len(arr1) m = len(arr2) dp = [[[-1 for i in range(MAX)] for j in range(MAX)] for k in range(MAX)] print(lcs(dp, arr1, n, arr2, m, k)) # This code is contributed by Rituraj Jain
C#
// C# program to find LCS of two arrays with
// k changes allowed in first array.
using System;
class GFG
{
static int MAX = 10;
// Return LCS with at most
// k changes allowed.
static int lcs(int[,,] dp, int[] arr1,
int n, int[] arr2,
int m, int k)
{
// If at most changes is less than 0.
if (k < 0)
return -10000000;
// If any of two array is over.
if (n < 0 || m < 0)
return 0;
// Making a reference variable
// to dp[n,m,k]
int ans = dp[n, m, k];
// If value is already calculated,
// return that value.
if (ans != -1)
return ans;
try
{
// calculating LCS with no changes made.
ans = Math.Max(lcs(dp, arr1, n - 1,
arr2, m, k),
lcs(dp, arr1, n,
arr2, m - 1, k));
// calculating LCS when
// array element are same.
if (arr1[n - 1] == arr2[m - 1])
ans = Math.Max(ans, 1 +
lcs(dp, arr1, n - 1,
arr2, m - 1, k));
// calculating LCS with changes made.
ans = Math.Max(ans, 1 +
lcs(dp, arr1, n - 1,
arr2, m - 1, k - 1));
} catch (Exception e) { }
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int k = 1;
int[] arr1 = { 1, 2, 3, 4, 5 };
int[] arr2 = { 5, 3, 1, 4, 2 };
int n = arr1.Length;
int m = arr2.Length;
int[,,] dp = new int[MAX, MAX, MAX];
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
for (int l = 0; l < MAX; l++)
dp[i, j, l] = -1;
Console.WriteLine(lcs(dp, arr1, n,
arr2, m, k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find LCS of two
// arrays with k changes allowed in
// first array.
let MAX = 10;
// Return LCS with at most k changes allowed.
function lcs(dp, arr1, n, arr2, m, k)
{
// If at most changes is less than 0.
if (k < 0)
return -10000000;
// If any of two array is over.
if (n < 0 || m < 0)
return 0;
// Making a reference variable
// to dp[n][m][k]
let ans = dp;
// If value is already calculated,
// return that value.
if (ans != -1)
return ans;
try
{
// Calculating LCS with no changes made.
ans = Math.max(lcs(dp, arr1, n - 1, arr2, m, k),
lcs(dp, arr1, n, arr2, m - 1, k));
// Calculating LCS when array element are same.
if (arr1[n - 1] == arr2[m - 1])
ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1,
arr2, m - 1, k));
// Calculating LCS with changes made.
ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1,
arr2, m - 1, k - 1));
} catch (e) { }
return ans;
}
// Driver Code
let k = 0;
let arr1 = [ 1, 2, 3, 4, 5 ];
let arr2 = [ 5, 3, 1, 4, 2 ];
let n = arr1.length;
let m = arr2.length;
let dp = new Array(MAX);
for(let i = 0; i < MAX; i++)
for(let j = 0; j < MAX; j++)
for(let l = 0; l < MAX; l++)
dp = -1;
document.write(lcs(dp, arr1, n, arr2, m, k));
// This code is contributed by shivanisinghss2110
</script>
Producción:
3
Complejidad temporal: O(N*M*K).
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA