Longest Common Subsequence | DP using Memoization | Python3 program to memoize recursive implementation of LCS problem ; Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] memoization applied in recursive solution ; base case ; if the same state has already been computed ; if equal , then we store the value of the function call ; store it in arr to avoid further repetitive work in future function calls ; store it in arr to avoid further repetitive work in future function calls ; Driver Code ; assign - 1 to all positions
maximum = 1000 NEW_LINE def lcs ( X , Y , m , n , dp ) : NEW_LINE INDENT if ( m == 0 or n == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ m - 1 ] [ n - 1 ] != - 1 ) : NEW_LINE INDENT return dp [ m - 1 ] [ n - 1 ] NEW_LINE DEDENT if ( X [ m - 1 ] == Y [ n - 1 ] ) : NEW_LINE INDENT dp [ m - 1 ] [ n - 1 ] = 1 + lcs ( X , Y , m - 1 , n - 1 , dp ) NEW_LINE return dp [ m - 1 ] [ n - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ m - 1 ] [ n - 1 ] = max ( lcs ( X , Y , m , n - 1 , dp ) , lcs ( X , Y , m - 1 , n , dp ) ) NEW_LINE return dp [ m - 1 ] [ n - 1 ] NEW_LINE DEDENT DEDENT X = " AGGTAB " NEW_LINE Y = " GXTXAYB " NEW_LINE m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE dp = [ [ - 1 for i in range ( maximum ) ] for i in range ( m ) ] NEW_LINE print ( " Length ▁ of ▁ LCS : " , lcs ( X , Y , m , n , dp ) ) NEW_LINE