COUNTPL - Đếm số Palindrome
Tác giả: ll931110
Ngôn ngữ: C++
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
int F[260];
string S;
bool pal[260][260];
int rec(int x)
{
if (x < 0) return 0;
if (F[x] > -1) return F[x];
int best = x;
for (int i = x; i >= 0; i--) if (pal[i][x]) best = min(best,rec(i - 1));
return F[x] = 1 + best;
}
int main()
{
// freopen("pl.in","r",stdin);
// freopen("pl.ou","w",stdout);
cin >> S;
int n = S.size();
for (int i = 0; i < n; i++) pal[i][i] = true;
for (int i = 0; i < n - 1; i++) pal[i][i + 1] = (S[i] == S[i + 1]);
for (int len = 3; len <= n; len++)
for (int i = 0; i <= n - len; i++)
{
int j = i + len - 1;
pal[i][j] = ((S[i] == S[j]) && pal[i + 1][j - 1]);
}
memset(F,-1,sizeof(F));
printf("%d\n", rec(n - 1));
}