Longest Subsequence Palindrome

주어진 문자열에서 최장 길이 회문을 찾는 방법이다.

펠린드롬의 특징을 사용해서 i < j 일때 s[i] == s[j] 이면 s(i + 1 ... j - 1)의 최장 서브 시퀀스 회문의 값에 +2를 해줄 수 있다.

s[i] != s[j]라면 s(i + 1 ... j)와 s(i ... j - 1)의 최장 서브 시퀀스 회문중 max값을 사용한다.

int dp[501][501];
int lps(string& s, int l, int r) {
	if(l > r) return 0;
	if(dp[l][r] != -1) return dp[l][r];
	if(l == r) return dp[l][r] = 1;
	if(s[l] == s[r]) return dp[l][r] = lps(s, l + 1, r - 1) + 2;
	return dp[l][r] = max(lps(s, l + 1, r), lps(s, l, r- 1));
}