7. Compute Longest Palindrome Subsequence (LPS) in any sequence using dynamic programming. For example, given a string character, the LPS is carac. You should write down the recurrence, bottom-up computation, and the entire solution by backtracking.