[BOJ] 1509 : 팰린드롬 분할

#include <stdio.h>
#include <string.h>

const int n_ = 2500 + 5;

int len, dp[n_][n_], res[n_];
char data[n_];

int main() {
	scanf("%s", data);
	len = strlen(data);

	for (int i = 1; i <= len; i++) dp[i][i] = 1;
	
	for (int i = 1; i <= len - 1; i++)
		if (data[i - 1] == data[i])
			dp[i][i + 1] = 1;

	for (int i = 2; i <= len - 1; i++)
		for (int j = 1; i + j <= len; j++)
			if (data[j - 1] == data[i + j - 1] && dp[j + 1][i + j - 1] == 1)
				dp[j][i + j] = 1;

	for (int i = 1; i <= len; i++) {
		if (res[i] == 0 || (res[i] > res[i - 1] + 1 && res[i] != 0))
			res[i] = res[i - 1] + 1;
		for (int j = i + 1; j <= len; j++)
			if (dp[i][j] && (res[j] == 0 || (res[j] > res[i - 1] + 1 && res[j] != 0)))
				res[j] = res[i - 1] + 1;
	}

	printf("%d", res[len]);

	return 0;
}