Longest Palindromic Subsequence

#include<bits/stdc++.h>

using namespace std;

int main()

{

    string s;

    cout << "Enter String :: ";

    cin >> s;

    int n = s.size();

    int dp[n][n];

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

    {

        for(int j=0; j<n; j++)

        {

            if(i == j)

                dp[i][j] = 1;

            else

                dp[i][j] = 0;

        }

    }

    for(int k=1; k<n; k++)

    {

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

        {

            int j = i+k;

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

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

            else

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

        }

    }

    cout << "Longest Palindromic Subsequence Size :: " << dp[0][n-1] << "\n";

    return 0;

}