[Leetcode] 516. Longest Palindromic Subsequence

문제 : https://leetcode.com/problems/longest-palindromic-subsequence/description/

---

주어진 문자열 s에서 가장 긴 회문 부분 수열의 길이를 찾으세요.

부분 수열이란 다른 수열에서 일부 또는 전혀 없애지 않고 남은 원소들의 순서를 변경하지 않고 유도할 수 있는 수열입니다.

---

DP로 풀 수 있습니다.

 

dp[i][j] = s[i~j] 의 부분 수열의 가장 긴 펠린드롬 길이.

dp[i][j] = dp[i+1][j-1] + 2 (s[i] == s[j])
         = max(dp[i+1][j], dp[i][j-1]) (s[i] != s[j])

점화식은 위와 같습니다.

 

만약, 문자열의 가장 앞과 뒤의 문자가 같다면 문자열의 가장 앞, 뒤 문자를 부분 수열에 포함하여 길이는 + 2가 되고 그 사이에 있는 문자열의 가장 긴 펠린드롬의 부분 수열 길이를 더합니다. 그래서 s[i] == s[j] 인 경우, dp[i+1][j-1] + 2.

ex) a~~~a 라면 가장 앞, 뒤 문자가 a로 동일하여 이를 부분 수열에 추가한 뒤 그 사이에 있는 문자열들 중 다시 최대길이를 구합니다.

 

문자열의 가장 앞과 뒤의 문자가 다르다면 문자열의 가장 앞 혹은 가장 뒤의 문자를 하나 제거한 경우의 부분 문자열에서 다시 정답을 구합니다.  이 둘 중 더 긴게 정답이 됩니다. 그래서 s[i] != s[j] 인 경우, dp[i+1][j] (가장 앞 제거), dp[i][j-1] (가장 뒤 제거) 중 더 큰게 최대길이가 됩니다.

 

시간, 공간 복잡도는 O(N^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/516.%20Longest%20Palindromic%20Subsequence.cpp