We are given a string s and need to find the longest palindromic subsequence.
To solve this, first, make a copy of the string s and store it as t.
Next, reverse the original string s to get s'.
The problem now becomes finding the longest common subsequence (LCS) between the string s and its reverse s'.
Using dynamic programming, we can compute the LCS of the two strings. The LCS between s and s' will give us the longest palindromic subsequence of s.
Finally, the length of the LCS is the length of the longest palindromic subsequence in the original string s.

Code

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

class Solution{
private:
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    int func(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();

        // Declare a 2D DP array to store length of the LCS
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));

        // Initialize first row and first column to 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }

        // Fill in the D