[백준] 14517 - 팰린드롬 개수 구하기 (Python)

부분수열 중 팰린드롬을 구해야 하므로 구간으로 접근해 보자.

구간 $[l-r]$에 대해서 구간 내의 모든 팰린드롬의 개수를 $DP(l, r)$라 하자. 점화식은 다음과 같다.

$DP(l, r) = DP(l+1, r) + DP(l, r-1)$

점화식을 보면 구간에 겹치는 부분이 생긴다는 것을 알 수 있는데, $[l+1, r-1]$ 구간에서 중복이 발생한다. 따라서 포함 배제의 원리에 따라 $DP(l+1, r-1)$ 을 빼 줘야 한다.

또한 문자열을 $S$라 하면 $S[l] == S[r]$ 인 경우가 있다.
$[l+1, r-1]$ 구간의 모든 팰린드롬에 대해 새로운 팰린드롬이 만들어지고 문자열 전체가 또 하나의 팰린드롬이 된다.
따라서 이 경우엔 $DP(l+1, r-1) + 1$를 더해준다.

---

def find(l, r):
    if dp[l][r]:
        return dp[l][r]
    if l == r:
        return 1 
    elif l > r:
        return 0 
    dp[l][r] = (find(l, r-1)+find(l+1, r)-find(l+1, r-1)) % mod
    if s[l] == s[r]:
        dp[l][r] = (dp[l][r] + find(l+1, r-1)+1) % mod
    return dp[l][r]
    
s = input()
mod = 10007
# 구간 [l-r]내의 모든 팰린드롬의 개수는 dp[l][r]
dp = [[0]*len(s) for _ in range(len(s))]
print(find(0, len(s)-1))