Longest Palindromic Subsequence

最长回文子序列, 首先这个子序列就是substring, 这题用dp做, dp[i][j]表示在substring(s, i, j)的最长回文子序列. 这时,有一下集中情况:

  • i==j, 这时候就是一个字符,当前最长回文子序列是1
  • i>j, 这时候越界了, 返回0
  • i<j时, 我们需要判断i和j的字符是不是相同,
    • 如果相同, 继续探索i+1和j-1的答案并且加上i和j作为答案,即+2
    • 如果不同, 则当前的i和j无法构成回文, 因为我们需要的是longest,所以选择i+1和j-1之间较大的那个.