$($a$)(7$ points$)$ A sub$-$sequence of a string is any ordered subset of characters of that string. palindrome is a string that reads the same backward as it does forward.

Given a string $\backslash ($ s $\backslash ),$ give a DP solution to find its longest sub$-$sequence that forms a palindror Your solution should take $\backslash ($ O$\backslash$left$($n$^\{2\}\backslash$right$)\backslash )$ time where $\backslash ($ n$=|$s$|\backslash ).$

Suppose $\backslash ($ s$=\backslash )$ "axdybdac". The longest palindromic sub$-$sequence is "adbda"

$\backslash (\backslash$mathrm$\{$a$\}(\mathrm{.}5)\backslash )$ Let $\backslash (\backslash$operatorname$\{$opt$\}(1,$ n$)\backslash )$ represents the length of the longest sub$-$sequence of that form palindrome.

$\backslash (\backslash$mathrm$\{$b$\}(\mathrm{.}5)\backslash ).$ Let opt $\backslash (($i$,$ j$)\backslash )$ represents the length of the longest sub$-$sequence of that form: palindrome.