Memoization ( 1D , 2D and 3D ) | Java 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 ; Utility function to get max of 2 integers ; Driver code
import java . io . * ; import java . lang . * ; class GFG { public static int arr [ ] [ ] = new int [ 1000 ] [ 1000 ] ; public static int lcs ( String X , String Y , int m , int n ) { if ( m == 0 n == 0 ) return 0 ; if ( arr [ m - 1 ] [ n - 1 ] != - 1 ) return arr [ m - 1 ] [ n - 1 ] ; if ( X . charAt ( m - 1 ) == Y . charAt ( n - 1 ) ) { arr [ m - 1 ] [ n - 1 ] = 1 + lcs ( X , Y , m - 1 , n - 1 ) ; return arr [ m - 1 ] [ n - 1 ] ; } else { arr [ m - 1 ] [ n - 1 ] = max ( lcs ( X , Y , m , n - 1 ) , lcs ( X , Y , m - 1 , n ) ) ; return arr [ m - 1 ] [ n - 1 ] ; } } public static int max ( int a , int b ) { return ( a > b ) ? a : b ; } public static void main ( String [ ] args ) { for ( int i = 0 ; i < 1000 ; i ++ ) { for ( int j = 0 ; j < 1000 ; j ++ ) { arr [ i ] [ j ] = - 1 ; } } String X = " AGGTAB " ; String Y = " GXTXAYB " ; int m = X . length ( ) ; int n = Y . length ( ) ; System . out . println ( " Length ▁ of ▁ LCS ▁ is ▁ " + lcs ( X , Y , m , n ) ) ; } }