Intuition

임의의 두 문자가 같거나 다른지에 따라 관계식에 변화가 있을 것이라고 추정했다.

Approach

문제 정의

$A[i][j]$ : $[i:j]$의 범위에서 Longest Palindromic Subsequence(이하 LPS)
Goal : $A[0][strlen(s)-1]$

위와 같이 문제를 정의한다.
길이가 1인경우에는 그 자체로 LPS이다.

baseCase : $A[i][j]=1$ $(i==j)$

점화식 세우기

임의의 두 원소가 같은 경우, 그 내부(직전) LPS의 길이에서 2만큼 늘어난다.

그렇지 않은 경우, $[i+1:j]$와 $[i:j-1]$의 범위 중 LPS가 더 큰 쪽의 값을 취한다.

점화식 :
$A[i][j]=\begin{cases} A[i+1][j-1] + 2\quad(s[i]==s[j])\\ MAX(A[i+1][j], A[i][j-1])\quad(s[i]!=s[j])\\ \end{cases}$

이때 i는 i+1에서 참조하고, j는 j-1에서 참조하므로
i는 역순으로, j는 순서대로 순회해야한다.

Solution

#include <string.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
int ans[1000][1000];

int longestPalindromeSubseq(char* s) {
    int len=strlen(s);

    ans[0][0]=1;
    for (int i=1;i<=len-1;i++){
        ans[i][i-1]=0;
        ans[i][i]=1;
    }

    for (int i=len-1;i>=0;i--){
        for (int j=i+1;j<=len-1;j++){
            if(s[i]==s[j]) ans[i][j]=ans[i+1][j-1]+2;
            else ans[i][j]=MAX(ans[i+1][j],ans[i][j-1]);
        }
    }  

    return ans[0][len-1]; 
}

사실 ans배열을 전역변수로 선언했기 때문에 0은 굳이 초기화시켜줄 필요는 없다.

Time Complexity

교수님께서 $O(N^2)$으로 교안에 작성해주셨다.

내가 생각하기에는 표로 보았을 때 대각선 기준으로 반절만 순회하기때문에 O(N)이 아닌가 싶다.

이 문제를 풀때 내가 놓쳤던 점은 너무 순방향(LIS처럼 앞에서 뒤로)으로만 풀이하려했고, 거기에만 집중했다는 점이다. 관계를 생각하기보다, 문제를 간단명료하게 잘 정의하는 것에 집중해보아야겠다.