A string is a palindrome if it is the same read left to right or right to left, e$.$g$.$ ababa. The longest palindrome subsequence of a string x is its longest subsequence $($of not necessarily consecutive symbols$)$ that is a palindrome. We want an algorithm to determine in time O$(|$x$|2)$ the length of the longest palindrome sub$-$sequence of a string x$.($a$)$ A cheap solution is$,$ let y be the reverse of x$,$ and apply the standard Longest Common Subsequence $($LCS$)$ algorithm to x and y$.$ This approach is numerically correct, but flawed, since the character locations for a LCS in x and y does not have to reference the same sequence of physical characters. Suppose x is ZABZA, what are the LCS for x and its reverse? How many are they? Are they all palindrome? $($b$)$ A better way is to design a new DP algorithm. Let l$($i$,$ j$)$ be the length of longest palindrome in x$[$i$,...,$ j$],$ please write the recurrence equations, including the initial conditions. Please analyze the time and space complexity.