팰린드롬

[백준 1509] 팰린드롬 분할 C++

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일단 문자열의 모든 범위에 따른 팰린드롬 여부를 2차원 table로 만들었다. dp[st][ed]에는 st부터 ed까지의 문자열이 팰린드롬인지 확인여부가 담겨있다. dp table을 채울 때 str[st]와 str[ed]가 같고 dp[st+1][ed-1]이 팰린드롬이면 dp[st][ed]도 팰린드롬인 성질을 이용해서 O(n^2)으로 테이블을 구할 수 ..