範例程式碼 uva11584

//uva11584
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool if_pd(const string& str, int s, int e) {
    while (s < e) {
        if (str[s] != str[e]) return false;
        ++s;
        --e;
    }
    return true;
}

int main() {
    int n = 0;

    cin >> n;
    for (int c = 0; c < n; c++) {
        string input = "";

        cin >> input;
        int l = input.size();
        vector<int> dp(l + 1, 0);

        dp[1] = 1;
        for (int i = 2; i <= l; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 0; j < i; j++) {
                if (if_pd(input, j, i - 1)) {
                    dp[i] = min(dp[j] + 1, dp[i]);
                }
            }
        }
        cout << dp[l] << endl;
    }
    return 0;
}