Minimice los elementos que se agregarán a una array dada de modo que contenga otra array dada como su subsecuencia

Dada una array A[] que consta de N enteros distintos y otra array B[] que consta de M enteros, la tarea es encontrar el número mínimo de elementos que se agregarán a la array B[] de modo que la array A[] se convierta en el subsecuencia de la array B[] .

Ejemplos:

Entrada: N = 5, M = 6, A[] = {1, 2, 3, 4, 5}, B[] = {2, 5, 6, 4, 9, 12} 
Salida: 3
Explicación:
A continuación se muestran el elemento que se necesita agregar:
1) Agregar 1 antes del elemento 2 de B[]
2) Agregar 3 después del elemento 6 de B[]
3) Agregar 5 en la última posición de B[].
Por lo tanto, la array resultante B[] es {1, 2, 5, 6, 3, 4, 9, 12, 5}.
Por tanto, A[] es la subsecuencia de B[] después de sumar 3 elementos.

Entrada: N = 5, M = 5, A[] = {3, 4, 5, 2, 7}, B[] = {3, 4, 7, 9, 2} 
Salida: 2 
Explicación: 
A continuación se muestran los elementos que se necesitan agregar: 
1) Agregar 5 después del elemento 4. 
2) Agregar 2 después del elemento 5. 
Por lo tanto, la array resultante B[] es {3, 4, 5, 2, 7, 9, 2}. 
Por lo tanto, se requieren 2 elementos para ser agregados.

Enfoque ingenuo: el enfoque ingenuo es generar todas las subsecuencias de la array B y luego encontrar esa subsecuencia de modo que al agregar un número mínimo de elementos de la array A para que sea igual a la array A. Imprime el recuento mínimo de elementos agregados.
Complejidad temporal: O(N*2 ^M )
Espacio auxiliar: O(M+N) 

Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . La idea es encontrar la subsecuencia común más larga entre las dos arrays A y B dadas . La observación principal es que el número mínimo de elementos que se agregarán en B[] de modo que A[] se convierta en su subsecuencia se puede encontrar restando la longitud de la subsecuencia común más larga de la longitud de la array A[] .

Por lo tanto, la diferencia entre la longitud del arreglo A[] y la longitud de la subsecuencia común más larga es el resultado requerido.

A continuación se muestra la implementación del enfoque anterior:

// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
int transformSubsequence(int n, int m,
                         vector<int> A,
                         vector<int> B)
{
     
    // Base Case
    if (B.size() == 0)
        return n;
 
    // dp[i][j] indicates the length of
    // LCS of A of length i & B of length j
    vector<vector<int>> dp(n + 1,
           vector<int>(m + 1, 0));
 
    for(int i = 0; i < n + 1; i++)
    {
        for(int j = 0; j < m + 1; j++)
        {
             
            // If there are no elements
            // either in A or B then the
            // length of lcs is 0
            if (i == 0 or j == 0)
                dp[i][j] = 0;
 
            // If the element present at
            // ith and jth index of A and B
            // are equal then include in LCS
            else if (A[i - 1] == B[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
 
            // If they are not equal then
            // take the max
            else
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j - 1]);
        }
    }
 
    // Return difference of length
    // of A and lcs of A and B
    return n - dp[n][m];
}
 
// Driver Code
int main()
{
    int N = 5;
    int M = 6;
 
    // Given sequence A and B
    vector<int> A = { 1, 2, 3, 4, 5 };
    vector<int> B = { 2, 5, 6, 4, 9, 12 };
 
    // Function call
    cout << transformSubsequence(N, M, A, B);
 
    return 0;
}
 
// This code is contributed by mohit kumar 29

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
static int transformSubsequence(int n, int m,
                                int []A, int []B)
{
  // Base Case
  if (B.length == 0)
    return n;
 
  // dp[i][j] indicates the length of
  // LCS of A of length i & B of length j
  int [][]dp = new int[n + 1][m + 1];
 
  for(int i = 0; i < n + 1; i++)
  {
    for(int j = 0; j < m + 1; j++)
    {
      // If there are no elements
      // either in A or B then the
      // length of lcs is 0
      if (i == 0 || j == 0)
        dp[i][j] = 0;
 
      // If the element present at
      // ith and jth index of A and B
      // are equal then include in LCS
      else if (A[i - 1] == B[j - 1])
        dp[i][j] = 1 + dp[i - 1][j - 1];
 
      // If they are not equal then
      // take the max
      else
        dp[i][j] = Math.max(dp[i - 1][j],
                            dp[i][j - 1]);
    }
  }
 
  // Return difference of length
  // of A and lcs of A and B
  return n - dp[n][m];
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 5;
  int M = 6;
 
  // Given sequence A and B
  int []A = {1, 2, 3, 4, 5};
  int []B = {2, 5, 6, 4, 9, 12};
 
  // Function call
  System.out.print(transformSubsequence(N, M, A, B));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for the above approach
 
# Function that finds the minimum number
# of the element must be added to make A
# as a subsequence in B
def transformSubsequence(n, m, A, B):
 
    # Base Case
    if B is None or len(B) == 0:
        return n
 
    # dp[i][j] indicates the length of
    # LCS of A of length i & B of length j
    dp = [[0 for col in range(m + 1)]
        for row in range(n + 1)]
 
    for i in range(n + 1):
 
        for j in range(m + 1):
 
            # If there are no elements
            # either in A or B then the
            # length of lcs is 0
            if i == 0 or j == 0:
                dp[i][j] = 0
 
            # If the element present at
            # ith and jth index of A and B
            # are equal then include in LCS
            elif A[i-1] == B[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
 
            # If they are not equal then
            # take the max
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 
    # Return difference of length
    # of A and lcs of A and B
    return n - dp[n][m]
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
    M = 6
     
    # Given Sequence A and B
    A = [1, 2, 3, 4, 5]
    B = [2, 5, 6, 4, 9, 12]
 
    # Function Call
    print(transformSubsequence(N, M, A, B))

// C# program for
// the above approach
using System;
class GFG{
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
static int transformSubsequence(int n, int m,
                                int []A, int []B)
{
  // Base Case
  if (B.Length == 0)
    return n;
 
  // dp[i,j] indicates the length of
  // LCS of A of length i & B of length j
  int [,]dp = new int[n + 1, m + 1];
 
  for(int i = 0; i < n + 1; i++)
  {
    for(int j = 0; j < m + 1; j++)
    {
      // If there are no elements
      // either in A or B then the
      // length of lcs is 0
      if (i == 0 || j == 0)
        dp[i, j] = 0;
 
      // If the element present at
      // ith and jth index of A and B
      // are equal then include in LCS
      else if (A[i - 1] == B[j - 1])
        dp[i, j] = 1 + dp[i - 1, j - 1];
 
      // If they are not equal then
      // take the max
      else
        dp[i, j] = Math.Max(dp[i - 1, j],
                            dp[i, j - 1]);
    }
  }
 
  // Return difference of length
  // of A and lcs of A and B
  return n - dp[n, m];
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 5;
  int M = 6;
 
  // Given sequence A and B
  int []A = {1, 2, 3, 4, 5};
  int []B = {2, 5, 6, 4, 9, 12};
 
  // Function call
  Console.Write(transformSubsequence(N, M,
                                     A, B));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program for the above approach
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
function transformSubsequence(n, m, A, B)
{
     
    // Base Case
    if (B.length == 0)
        return n;
 
    // dp[i][j] indicates the length of
    // LCS of A of length i & B of length j
    var dp = Array.from(Array(n+1), ()=>Array(m+1).fill(0));
 
    for(var i = 0; i < n + 1; i++)
    {
        for(var j = 0; j < m + 1; j++)
        {
             
            // If there are no elements
            // either in A or B then the
            // length of lcs is 0
            if (i == 0 || j == 0)
                dp[i][j] = 0;
 
            // If the element present at
            // ith and jth index of A and B
            // are equal then include in LCS
            else if (A[i - 1] == B[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
 
            // If they are not equal then
            // take the max
            else
                dp[i][j] = Math.max(dp[i - 1][j],
                               dp[i][j - 1]);
        }
    }
 
    // Return difference of length
    // of A and lcs of A and B
    return n - dp[n][m];
}
 
// Driver Code
 
var N = 5;
var M = 6;
 
// Given sequence A and B
var A = [1, 2, 3, 4, 5 ];
var B = [2, 5, 6, 4, 9, 12 ];
 
// Function call
document.write( transformSubsequence(N, M, A, B));
 
 
 
</script>

3

Complejidad de tiempo: O(M*M), donde N y M son las longitudes de la array A[] y B[] respectivamente.
Espacio auxiliar: O(M*N)