We know what's a palindrome is? A palindrome is a string that is the same as its reverse order.

That means to find the longest palindromic subsequence, we need to check the longest common subsequence between the string itself and its reverse string.

So, basically

    LPS(s) = LCS(s,reverse(s))
    
    Where,
    LPS(s) = longest palindromic subsequence for string s
    LCS(s,reverse(s)) = Longest Common subsequence for 
                        string s and reverse of string s 

So, to find the longest palindromic subsequence:

1. Find the reverse of the string
2. Do an LCS between the string and its reverse string
3. Result=string length-longest palindromic subsequence length

1) To find the reverse of the string

    string reverse(string s,int n){
        string p="";
        for(int i=n-1;i>=0;i--)
            p+=string(1,s[i]); //append characters from last    
        return p;
    }

2) LCS between the string and its reverse string

To detail how to find Longest Common subsequence b/w any two strings, go through this article, Longest Common subsequence

    L = length of the string,reverse of the string
    Str1 = string itself
    Str2 = Reverse of the string

    1.  Initialize DP[l+1][l+1]  to 0
    2.  Convert the base case of recursion:
            for i=0 to l
                DP[i][0]=0;
            for i=0 to l
                DP[0][i]=0;

        Fill the DP table 
        for i=1 to l    //i be the subproblem length for the string
            for j=1 to l //j be the subproblem length for reverse of the string
                if(str1[i-1]==str2[j-1]) 
                    DP[i][j]=DP[i-1][j-1]+1;
                else
                    DP[i][j]=max(DP[i-1][j],DP[i][j-1]);
            end for
        end for  

    4.  The final output will be DP[l][l]
 
    Final step is to return minimum number of deletion which l-DP[l][l]

    This will lead to the final result.

There is another way to find the longest palindromic subsequence, without using LCS. I wouldn't explain the detailed solution, rather try to think and implement your own.

The recursion is,

    LPS(I,j) = LPS(i+1,j-1)+2 
    if 
        str1[i] == str[j]
    Else 
        LPS(I,j) = max(LPS(i+1,j), LPS(i,j-1))

Convert the above recursion into DP while taking care of base cases.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

string reverse(string s, int n)
{
    string p = "";
    
    for (int i = n - 1; i >= 0; i--)
        p += string(1, s[i]);

    return p;
}

//LCS of the strings
int LCS(string s1, string s2, int n)
{

    int dp[n + 1][n + 1];
    
    for (int i = 0; i <= n; i++)
        dp[0][i] = 0;

    for (int i = 0; i <= n; i++)
        dp[i][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = std::max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    
    return dp[n][n];
}

int main()
{

    string s1;
    
    cout << "Enter string:\n";
    cin >> s1;
    
    int n = s1.length();
    
    //reverse of string
    string s2 = reverse(s1, n);
    
    //find LCS of the strings, result=n-LCS(s1,s2)
    cout << "minimum characters to remove " << n - LCS(s1, s2, n) << endl;
    
    return 0;
}

Output

Enter string:
includecpni
minimum characters to remove 4