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
def transformSubsequence ( n , m , A , B ) : NEW_LINE INDENT if B is None or len ( B ) == 0 : NEW_LINE INDENT return n NEW_LINE DEDENT dp = [ [ 0 for col in range ( m + 1 ) ] for row in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( m + 1 ) : NEW_LINE INDENT if i == 0 or j == 0 : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT elif A [ i - 1 ] == B [ j - 1 ] : NEW_LINE INDENT dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return n - dp [ n ] [ m ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 5 NEW_LINE M = 6 NEW_LINE A = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE B = [ 2 , 5 , 6 , 4 , 9 , 12 ] NEW_LINE print ( transformSubsequence ( N , M , A , B ) ) NEW_LINE DEDENT