[코딩테스트 연습] 가장 긴 팰린드롬

 

https://programmers.co.kr/learn/courses/30/lessons/12904

---

hyozkim님의 풀이를 보고 해결하였습니다. (https://velog.io/@sa833591/%EA%B0%80%EC%9E%A5-%EA%B8%B4-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv.3)

 

팰린드롬을 위한 dp 점화식은 간단합니다.

 

D[i][j] == 1 : i번째 문자부터 ~ j번째 문자가 팰린드롬이면 1
D[i][j] == 0 : i번째 문자부터 ~ j번째 문자가 팰린드롬이 아니면 0

 

기저 사례는 아래와 같습니다.

DP[i][i] = 1

DP[i][i+1] = (str[i] == str[i+1] ? 1 : 0) 

 

이 다음에 문자열이 3개 이상부터 점화식을 확장해 나가는 방식은

DP[i][j] = str[i] == str[j] 이고 && DP[i+1][j-1] = 1 이면, DP[i][j] =1 입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG12904.cc