Minimize elements to be added to a given array such that it contains another given array as its subsequence | C ++ 14 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 ; Base Case ; dp [ i ] [ j ] indicates the length of LCS of A of length i & B of length j ; If there are no elements either in A or B then the length of lcs is 0 ; If the element present at ith and jth index of A and B are equal then include in LCS ; If they are not equal then take the max ; Return difference of length of A and lcs of A and B ; Driver Code ; Given sequence A and B ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int transformSubsequence ( int n , int m , vector < int > A , vector < int > B ) { if ( B . size ( ) == 0 ) return n ; 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 ( i == 0 or j == 0 ) dp [ i ] [ j ] = 0 ; else if ( A [ i - 1 ] == B [ j - 1 ] ) dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] ; else dp [ i ] [ j ] = max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ; } } return n - dp [ n ] [ m ] ; } int main ( ) { int N = 5 ; int M = 6 ; vector < int > A = { 1 , 2 , 3 , 4 , 5 } ; vector < int > B = { 2 , 5 , 6 , 4 , 9 , 12 } ; cout << transformSubsequence ( N , M , A , B ) ; return 0 ; }