26 longest palindrome subsequence.cpp

int lcs(int n, int m, string A, string B){
        // here n is the length of string A and m is length for string B  
// make table size depend on change input/variable 
        int t[n+1][m+1];

//intializing first row and first col based on base condition of recusive solution 
        for(int i=0; i<n+1; i++){
            for(int j=0;j<m+1; j++){
                if(i==0 || j==0){
                    t[i][j] = 0;
                }
            }
        }
        
// filling other t[][] box    base on choice diagram   
        for(int i=1; i<n+1; i++){
            for(int j=1; j<m+1; j++){
                if(A[i-1]==B[j-1]){
                    t[i][j] = 1 + t[i-1][j-1]; 
                }
                
                else {
                    t[i][j] = max( t[i][j-1],t[i-1][j] );
                }
            }
        }
        
        return t[n][m];
    }
    int longestPalinSubseq(string A) {
        
        // LPS of string A = LCS of (string A , reverse of string A)
        // so reverse string A and store in a string B 
        string B = A;
        reverse(B.begin(),B.end() );
        
        int length_of_LPS = lcs(A.length(),B.length(),A,B);
        
        return  length_of_LPS;
      
    }