백준 #1509 팰린드롬 분할 : 점화식

1~e 까지의 문자열 중 팰린드롬으로 쪼개되 그 수가 가장 작게 하는 갯수를 dp 배열에 저장한다.

dp[e]는 e로 끝나는 문자열 중에 팰린드롬인 문자열의 시작을 s 라고 놓으면,

모든 s에 대해서 dp[s-1]+1이 된다. 이중에 min 값이 곧 dp[e] 값이 된다.

​

dp 배열을 기본적으로 무한대로 정의한다.

a~b가 팰린드롬인 경우를 true, 아니면 false 의 방식으로 bool 2차원배열로 저장한다.

위 점화식을 이용해서 dp 배열을 앞에서부터 채워나가면 된다.

​

>>>>처음에 재귀를 이용해서 i~x 까지 팰린드롬인 모든 x 에 대해서 i= x+1로 다시 재귀를 타는 방법으로 모든 팰린드롬 부분집합 조합을 다 확인하고 원소 개수를 세어서 그중 가장 작은걸로 고르는 방법을 시도했는데,, 재귀마다 for문을 돌기 때문에 2500짜리 문자열을 체크하기에는 정신나간 방법이었다. 컴팩트하게 min 값을 구하는 점화식을 사용해야 시간 안에 답을 도출할 수 있다.