Our goal is to find the longest palindromic subsequence in a given sequence. For example, we are given a sequence "ABCBAD". The longest palindromic subsequence is "ABCBA". Now let $s$ is the given sequence and we use $s[i]$ to denote the $i^\text{th}$ character in $s$. In addition, we let $L[i, j]$ denote the length of longest palindromic subsequence in $s[i:j]$ (from $s[i]$ to $s[j]$). If $s[i:j]$ is palindromic, then the front character $s[i]$ and the last character $s[j]$ should be the same. We can also say that: $$L[i, j] = L[i+1, j-1] + 2$$ On the other hand, if $s[i:j]$ is not palindromic (or, $s[i]\neq s[j]$), then: $$L[i, j] = max(L[i+1, j], L[i, j-1])$$ We can follow this rule to solve this problem recursively. First, we can consider the longest palindromic subsequence when $i=j$: Because the length of $s[i:j]$ is 1, $L[i, j]=1$. Next, we consider $j = i+1$. $L[i, j]$ will be 2 only when $s[i]=s[j]$; otherwise, $L[i, j]=1$. Next ...