[DP] BOJ 1509 펠린드롬 분할

 

import sys
sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
 
arr = input()
N = len(arr)
p = [[0] * N for _ in range(N)]
dp = [N] * (N + 1)
 
 
for i in range(N): # 1개짜리 문자열
    p[i][i] = 1
for i in range(N - 1): # 2개짜리 문자열
    if arr[i] == arr[i + 1]: p[i][i + 1] = 1
 
 
for interval in range(2, N): # 3 이상 문자열
    for start in range(N - interval):
        end = start + interval 
        if arr[start] == arr[end] and p[start + 1][end - 1] == 1:
            p[start][end] = 1
 
# 여기까진 BOJ 10942와 동일
 
dp[0] = 0
for end in range(1, N + 1):
    for start in range(1, end + 1):
        if p[start - 1][end - 1]: # 펠린드롬일 경우
            dp[end] = min(dp[end], dp[start - 1] + 1)
         
print(dp[N])