A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes). Design a dynamic programming algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac.