1) 문제 정의주어진 sequence에서 가장 긴 palindromic한 subsequence를 출력한다. 여기서 palindromic은 왼쪽에서부터 읽으나 오른쪽에서부터 읽으나 동일하게 읽히는 것을 의미한다. 예시로 다음의 sequence가 있다하자.여기에서 subsequence A B B A는 palindromic하다. 그리고 여기서 가장 긴 palindromic은 A B G G B A 이다.여기서 sequence는 사용자가 그 길이와 해당 요소를 입력하고 출력은 선택된 subsequence의 길이와 그 해당 요소를 출력한다. 그리고 해당 알고리즘은 O(n^2) 안에 실행되어야 한다.2) recurrence relation 증명 및 설명L(i, j) 를 ai, ... ,aj로 이루어진 sequence에서 가장 긴 palindromic 한 subsequence의 길이라 하자 그럴 경우 L(i, j)는 다음의 recurrence relation을 만족하게 된다.첫 번째의 경우는 입력된 sequence의 길이가 1인 경우이다. 예로는 subsequence 가 1 2 1인 경우로 양 옆의 1 1을 지우고 2일 때 앞으로 읽으나 뒤로 읽으나 그 읽힘이 동일하기에 sequence 에 포함한다. 따라서 1을 추가시킨다.두 번째의 경우 입력된 sequence 의 길이가 2이고 두 개의 값이 같은 경우이다. 이 때는 이것만으로 subsequence 가 만족이되고 sequence 가 끝남으로 2를 반환해준다.
