Longest Common Subsequence | DP using Memoization | Javascript 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
let maximum = 1000 ; function lcs ( X , Y , m , n , dp ) { if ( m == 0 n == 0 ) { return 0 ; } if ( dp [ m - 1 ] [ n - 1 ] != - 1 ) { return dp [ m - 1 ] [ n - 1 ] ; } if ( X [ m - 1 ] == Y [ n - 1 ] ) { dp [ m - 1 ] [ n - 1 ] = 1 + lcs ( X , Y , m - 1 , n - 1 , dp ) ; return dp [ m - 1 ] [ n - 1 ] ; } else { dp [ m - 1 ] [ n - 1 ] = Math . max ( lcs ( X , Y , m , n - 1 , dp ) , lcs ( X , Y , m - 1 , n , dp ) ) ; return dp [ m - 1 ] [ n - 1 ] ; } } let X = " " ; let Y = " " ; let m = X . length ; let n = Y . length ; let dp = new Array ( m ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( maximum ) ; for ( let j = 0 ; j < dp [ i ] . length ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } document . write ( " " + lcs ( X , Y , m , n , dp ) ) ;