#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define itn int
#define retrun return
#define _memset(a) memset((a), 0, sizeof((a)))
int dp[1010];
char s[1010];
bool judge(int l, int r) {
while (l < r) {
if (s[l] != s[r]) return 0;
l++;
r--;
}
return 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
cin >> (s + 1);
int len = strlen(s + 1);
for (int i = 1; i <= len; i++) {
dp[i] = i;
for (int j = 0; j <= i; j++) {
if (judge(j + 1, i)) dp[i] = min(dp[j] + 1, dp[i]);
}
}
cout << dp[len] << endl;
}
//system("pause");
return 0;
}
相关文章
- 10-23新手村-过程函数与递归-P1217 [USACO1.5]回文质数 Prime Palindromes
- 10-23例题 9-7 划分成回文串(Partitoning by Palindromes, UVa 11584)
- 10-231689. Partitioning Into Minimum Number Of Deci-Binary Numbers
- 10-23【LeetCode】132.Palindrome Partitioning II
- 10-23Codeforces Round #746 (Div. 2) C - Bakry and Partitioning(dfs 异或技巧 思维)
- 10-23【题解】AT3591 Yet Another Palindrome Partitioning
- 10-23动态规划之132 Palindrome Partitioning II
- 10-23CF寒假补题集——B. Palindromes Coloring
- 10-23Codeforces 570E - Pig and Palindromes - [滚动优化DP]
- 10-23luogu1207双重回文数[usaco1.2]Dual Palindromes