Question $2(30$ points$)$

Palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are civic, racecar, and aibohphobia $($fear of palindromes$).$

Write an algorithm using Dynamic programming approach to find the longest palindrome subsequence. For example, given the input character, your algorithm should return $5,$ because the longest palindrome subsequence is carac.

$(5$ points$)$ First explain your high$-$level idea.

$(10$ points$)$ Write the recurrence relation for your algorithm?

$(10$ points$)$ Write the algorithm

$(5$ points$)$ What is the time complexity of your algorithm