Longest Palindromic Subsequence-dynamic programming
in a string we should find the longest palindromic subsequence's length in s.
examples:
Input:
"bbbab"
longest subsequence is bbbb and its length is 4
Output:
4
Input:
"bbabcbcab"
Output:
7
lets use dynamic programming to solve this question:
c++ implementation:
t is the no.of test cases:
examples:
Input:
"bbbab"
longest subsequence is bbbb and its length is 4
Output:
4
Input:
"bbabcbcab"
Output:
7
lets use dynamic programming to solve this question:
c++ implementation:
t is the no.of test cases:
#include <bits/stdc++.h>
using namespace std;
int longestPalindromeSubseq(string s) {
int l=s.size();
int i, j,k;
int table[l][l];
for(i=0; i<l; i++)
for(j=0; j<l; j++)
table[i][j]=0;
for(i=0; i<l; i++)
table[i][i]=1;
for(i=0; i<l-1; i++)
{ if(s[i]==s[i+1])
table[i][i+1]=2;
else
table[i][i+1]=1;
}
for(k=3; k<=l; k++)
{ for(i=0; i<l-k+1; i++)
{
j=i+k-1;
if(s[i]==s[j])
table[i][j]=table[i+1][j-1]+2;
else
table[i][j]=max(table[i][j-1],table[i+1][j]);
}
}
return table[0][l-1];
}
int main()
{
int t; cin>>t;
while(t--)
{
string s;cin>>s;
cout<<longestPalindromeSubseq(s);
cout<<endl;
}
return 0;
}