Longest Palindromic Subsequence By Dynamic Programming

#include<bits/stdc++.h>

using namespace std;

int lps(string s)

{

    int n = s.size(), i, j, k;

    int L[n][n];

    for(i=0;i<n;i++)

        L[i][i] = 1;

    for(k=2;k<=n;k++)

    {

        for(i=0;i<n-k+1;i++)

        {

            j = i+k-1;

            if(s[i] == s[j] && k == 2)  // k == 2 cz its indicate start

                L[i][j] = 2;

            else if(s[i] == s[j])

                L[i][j] = L[i+1][j-1] + 2;

            else

                L[i][j] = max(L[i][j-1], L[i+1][j]);

        }

   }

   return L[0][n-1];

}

int main()

{

    string s;

    cout << "Enter A String :: ";

    cin >> s;

    cout << "Longest Palindrome Subsequence Size :: " << lcs(s) << "\n";

    return 0;

}