Memoization ( 1D , 2D and 3D ) | 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
def lcs ( X , Y , m , n ) : NEW_LINE INDENT global arr NEW_LINE if ( m == 0 or n == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( arr [ m - 1 ] [ n - 1 ] != - 1 ) : NEW_LINE INDENT return arr [ m - 1 ] [ n - 1 ] NEW_LINE DEDENT if ( X [ m - 1 ] == Y [ n - 1 ] ) : NEW_LINE INDENT arr [ m - 1 ] [ n - 1 ] = 1 + lcs ( X , Y , m - 1 , n - 1 ) NEW_LINE return arr [ m - 1 ] [ n - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT arr [ m - 1 ] [ n - 1 ] = max ( lcs ( X , Y , m , n - 1 ) , lcs ( X , Y , m - 1 , n ) ) NEW_LINE return arr [ m - 1 ] [ n - 1 ] NEW_LINE DEDENT DEDENT / * Utility function to get max of 2 integers * / NEW_LINE arr = [ [ 0 ] * 1000 ] * 1000 NEW_LINE for i in range ( 0 , 1000 ) : NEW_LINE INDENT for j in range ( 0 , 1000 ) : NEW_LINE INDENT arr [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT X = " AGGTAB " NEW_LINE Y = " GXTXAYB " NEW_LINE m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE print ( " Length ▁ of ▁ LCS ▁ is ▁ " , lcs ( X , Y , m , n ) ) NEW_LINE