範例程式碼 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;
}