가장 긴 팰린드롬 부분 수열 (subsequence)

https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/

~~~

이 문제에 대한 naive solution은 주어진 sequence의 모든 부분 sequences를 생성하고, 가장 긴 palindromic subsequence를 찾는 것이다. 이 솔루션은 시간 복잡도에서 exponential이다. 이 문제가 DP 문제의 중요한 특성들을 어떻게 가지는지와 DP를 사용해서 어떻게 해결될 수 있는지를 봐보자.

1) Optimal Substructure
X[0..n-1]이 길이 n의 input sequence라고 하고, L(0, n-1)이 X[0..n-1]의 가장 긴 팰린드롬 부분수열의 길이라고 하자.

만약 X의 마지막과 첫 번째 문제가 같다면, 그러면 L(0, n -1) = L(1, n -2) + 2이다.
그렇지 않다면, L(0, n -1) = MAX( L(1,n -1), L(0, n-2)) 이다.

다음은 모든 경우가 처리되는 일반적인 재귀 솔루션이다.

```
// 모든 단일 문자는 길이가 1인 팰린드롬이다.
L(i, i) = 1  주어진 수열의 모든 인덱스 i에 대해.

// 만약 첫 번째와 마지막 문자가 같지 않다면
if(X[i] != X[j]) L(i, j) = max{ L(i + 1, j), L(i, j - 1)}

// 만약 두 개의 문자만 있고, 둘 다 같다면
Else if(j == i + 1) L(i, j) = 2

// 만약 두 개 이상의 문자들이 있고, 첫 번째와 마지막 문자가 같다면
Else L(i,j) = L(i + 1, j - 1) + 2

```

2) Overlapping Subproblems
다음은 LPS 문제의 간단한 재귀 구현이다. 그 구현은 간단히 위에서 언급된 재귀 구조를 따른다.

~~


위의 구현을 고려하면, 다음은 모든 다른 문자들을 가진 길이가 6인 한 수열에 대한 부분적인 재귀 트리이다.

위의 부분 재귀 트리에서, L(1,4)는 두 번 풀어진다. 만약 우리가 완전한 재귀 트리를 그린다면, 그러면 우리는 또 다시 해결되는 많은 subproblems들이 있다는 것을 볼 수 있다. 같은 subproblems가 또 다시 호출되기 때문에, 이 문제는 overlapping Subproblems 특징을 가진다. 그래서 LPS 문제는 DP의 두 가지 특성을 가진다. (see this and this). 다른 일반적인 DP문제 처럼, 같은 부분 문제들의 재연산은 bottm up 방식으로 임의의 배열 L[][]을 구성하여 피해질 수 있다.

~~~

위의 구현의 시간 복잡도는 O(n^2)이고, Naive Recursive Implementation의 시간 복잡도 보다 최악의 경우에 더 좋다.

이 문제는 Longest Common Subsequence(LCS) 문제와 가깝다. 사실, 우리는 이 문제를 해결하는 subroutine으로서 LCS를 사용할 수 있다.다음은 LCS를 사용하는 두 단계 솔루션이다.

1) 주어진 수열을 반대로 뒤집고, 그 반대를 다른 배열 rev[0..n-1]에 저장해라.
2) 주어진 수열과 rev[]의 LCS는 가장 긴 palindromic sequence가 될 것이다.

이 해결책은 또한 O(n^2) 솔루션이다.