COUNTPL - Đếm số Palindrome
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#include <string.h>
int main()
{
// freopen("COUNTPL.in","r",stdin);
int f[256];
bool a[256][256];
char s[256];
scanf("%s",s);
int n = strlen(s);
for(int i = 0;i<n;i++)
{
for(int j = 0;j<=n-1-i;j++)
{
if(i==0) a[j][j]= true;
else if(i==1)
{
if(s[j]==s[j+1]) a[j][j+1]=true;
else a[j][j+1]= false;
}
else
{
if(s[j]!=s[j+i]) a[j][j+i]=false;
else a[j][j+i]=a[j+1][j+i-1];
}
}
}
f[0]=1;
for(int i = 1;i<=n-1;i++)
{
if(a[0][i]) f[i]=1;
else
{
int min = 1000;
for(int j = 1;j<=i;j++)
if(a[j][i] && f[j-1]+1<min)
min = f[j-1]+1;
f[i]=min;
}
}
printf("%d",f[n-1]);
//getch();
}