46 lines
1.1 KiB
C
46 lines
1.1 KiB
C
#include <stdio.h>
|
|
#include <stdbool.h>
|
|
#include <string.h>
|
|
|
|
bool isPalindrome[2500][2500];
|
|
char str[2501];
|
|
int dp[2500];
|
|
|
|
int main() {
|
|
scanf("%s", str);
|
|
int length = strlen(str);
|
|
|
|
isPalindrome[0][0] = true;
|
|
for(int i=1; i<length; i++) {
|
|
isPalindrome[i][i] = true;
|
|
|
|
if(str[i-1] == str[i]) {
|
|
isPalindrome[i-1][i] = true;
|
|
}
|
|
}
|
|
|
|
for(int len = 3; len <= length; len++) {
|
|
for(int start = 0; start <= length - len; start++) {
|
|
int end = start + len - 1;
|
|
|
|
if(str[start] == str[end] && isPalindrome[start+1][end-1]) {
|
|
isPalindrome[start][end] = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
for(int i=0; i<length; i++) dp[i] = length;
|
|
|
|
for(int end=0; end<length; end++) {
|
|
for(int start=0; start <=end; start++) {
|
|
if(isPalindrome[start][end]) {
|
|
if(start == 0) dp[end] = 1;
|
|
else dp[end] = (dp[end] < dp[start-1] + 1) ? dp[end] : dp[start-1] + 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
printf("%d\n", dp[length-1]);
|
|
|
|
return 0;
|
|
} |