516. Longest Palindromic Subsequence

516. Longest Palindromic Subsequence

https://leetcode.com/problems/longest-palindromic-subsequence/

문제

풀이

Example1 DP표

분할 정복으로 푸는 문제이다. Example1으로 예를 들자면
1. dp[0][0] = "b"일 때 길이가 1일 때에는 항상 팔린드롬이므로 1을 저장한다.
2. dp[1][1]~dp[4][4]도 마찬가지로 "b","b","a","b"이므로 항상 1이다.
3. 길이가 1일 때를 확인했으므로 길이가 2일 때를 확인해야한다.
4. dp[0][1] = "bb"에서 s[0] = s[1]이 같으므로 2를 저장한다.
5. dp[1][2] = "bb"에서 s[1] = s[2]이 같으므로 2를 저장한다.
6. dp[2][3] = "ba"에서 s[2] = s[3]이 다르므로 dp[2][2], dp[3][3]중 최대값인 1을 저장한다.
7. dp[3][4] = "ab"에서 s[3] = s[4]이 다르므로 dp[3][3], dp[4][4]중 최대값인 1을 저장한다.
8. 길이가 2일 때를 확인했으므로 길이가 3일 때를 확인해야한다.
9. dp[0][2] = "bbb"에서 s[0] = s[2]가 같으므로 dp[1][1]을 확인한다.
즉 2+dp[1][1] = 3을 저장한다.
10. dp[1][3] = "bba"에서 s[1] = s[3]이 다르므로 dp[1][2], dp[2][3]에서 최대값을 저장한다.
이런식으로 분할 정복하여 최종값을 찾는 알고리즘으로 구현하였다.

결과