[Python] 프로그래머스 / 가장 긴 팰린드롬

문제 링크

 

이걸 DP가?

이 그림을 유심히 봐보면 알 수 있다.

 

그러므로, string의 i부터 j까지가 팰린드롬인지를 저장하는 dp matrix를 만들어서, dp를 해내가면 된다!

 

정답 코드

def solution(s):
    
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    
    for i in range(n) :
        dp[i][i] = True
        
    answer = 1

    for i in range(n-1) :
        if s[i] == s[i+1] :
            dp[i][i+1] = True
            answer = 2
            
    for length in range(3, n+1) :
        for i in range(n-length+1) :
            j = i + length - 1
            
            if s[i] == s[j] and dp[i+1][j-1] :
                dp[i][j] = True
                
                answer = max(answer, length)
    
    return answer