Minimize elements to be added to a given array such that it contains another given array as its subsequence | 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
function transformSubsequence ( n , m , A , B ) { if ( B . length == 0 ) return n ; 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 ( i == 0 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 ] = Math . max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ; } } return n - dp [ n ] [ m ] ; } var N = 5 ; var M = 6 ; var A = [ 1 , 2 , 3 , 4 , 5 ] ; var B = [ 2 , 5 , 6 , 4 , 9 , 12 ] ; document . write ( transformSubsequence ( N , M , A , B ) ) ;