Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
var s:string;
    i,j,n:longint;
    f:array[0..255] of longint;
    d:array[0..255,0..255] of boolean;

begin
     readln(s);
     n:=length(s);
     for i:=1 to n do d[i,i]:=true;
     for i:=1 to n-1 do
         if s[i]=s[i+1] then d[i,i+1]:=true;
     for j:=3 to n do
         for i:=1 to n-j+1 do
             d[i,i+j-1]:=d[i+1,i+j-2] and (s[i]=s[i+j-1]);
     for i:=1 to n do f[i]:=300;
     for i:=1 to n do
         for j:=0 to i-1 do
             if d[j+1,i] then f[i]:=min(f[i],f[j]+1);
     writeln(f[n]);
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 260

char s[N]; int f[N][N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    scanf("%s",s); int n = strlen(s);
    fo(len,1,n) rep(i,n+1-len) {
        int j = i+len-1;
        if(len == 1) f[i][j] = 1;
        else if(len == 2) f[i][j] = s[i] == s[j] ? 1 : 2;
        else if( s[i] == s[j] && f[i+1][j-1] == 1 ) f[i][j] = 1;
        else {
            f[i][j] = len;
            fo(k,i,j-1) f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]);
        }
    }
    printf("%d\n", f[0][n-1]);
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>

#define REP(i, a, b) for(int i = (a); i <= (b); ++i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define endl '\n'

const int N = 500;

using namespace std;

bool isPalin[N][N];
int f[N], trace[N];
char s[N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    REP(i, 1, n) isPalin[i][i] = isPalin[i + 1][i] = 1;
    REPD(i, n, 1) REP(j, i + 1, n)
        isPalin[i][j] = s[i] == s[j] && isPalin[i + 1][j - 1];
    REP(i, 1, n) {
        f[i] = n;
        REPD(j, i, 1)
            if (isPalin[j][i] && f[i] > f[j - 1]) {
                f[i] = f[j - 1] + 1;
                trace[i] = j;
            }
    }
    cout << f[n] << endl;
        /*
    vector<string> ans;
    for (int i = n; i; i = trace[i] - 1) {
        string palin = "";
        REP(j, trace[i], i) palin += s[j];
        ans.push_back(palin);
    }
    reverse(ans.begin(), ans.end());
    for(vector<string>::iterator it = ans.begin(); it != ans.end(); ++it)
        cout << *it << endl;
        */
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i=a; i<=b; i++)
using namespace std;

int main() {
    char s[300];
    gets(s);
    int n = strlen(s)-1;
    int f[300];
    bool dx[300][300];
    FOR(i,0,n) {
        dx[i][i] = true;
        if (i) dx[i][i-1] = true;
    }
    FOR(l,1,n)
    FOR(i,0,n-l) {
        int j = i + l;
        dx[i][j] = dx[i+1][j-1] & (s[i] == s[j]);
    }

    FOR(i,0,n) {
        if (dx[0][i]) f[i] = 1;
        else f[i] = n+10;
        FOR(j,0,i-1)
            if (dx[j+1][i])
                f[i] = min(f[i], f[j]+1);
    }
    printf("%d",f[n]);
    return 0;
}

Code mẫu của hieult

#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();
}

Code mẫu của ll931110

#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));
}