countpl.cpp

#include<iostream>
#include<cstdlib>
#include<vector>

#define long long long
#define nln '\n'

using namespace std;

bool palindrome(string str)
{
    if (!str.size())
        return 1;

    long lef, rig;
    if (str.size() % 2 == 0)
        lef = str.size()/2-1, rig = lef+1;
    else
        lef = str.size()/2, rig = lef;

    while (lef >= 0 && rig <= (long)str.size()-1){
        if (str[lef] != str[rig])
            return 0;
        --lef; ++rig;
    }
    return 1;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    //freopen("palin.inp", "r", stdin);
    string str;
    getline(cin, str, nln);
    str = '&'+str;
    long n = str.size()-1;

    vector<long> dp(n+1, 300);
    dp[0] = 0;
    for (long i = 1; i <= n; ++i)
        for (long j = 0; j < i; ++j)
            if (dp[j]+1 < dp[i] && palindrome(str.substr(j+1, i-j)))
                dp[i] = dp[j]+1;
    cout << dp[n] << nln;
    return 0;
}