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之间较大的那个.

public class Solution {
    public int longestPalindromeSubseq(String s) {
        return rec(s,0,s.length() - 1, new Integer[s.length()][s.length()]);
    }
    private int rec(String s, int i, int j, Integer[][] memo) {
        if(memo[i][j] != null)
            return memo[i][j];
        if(i > j)
            return 0;
        if(i == j)
            return 1;
        if(s.charAt(i) == s.charAt(j))
            memo[i][j] = rec(s,i+1,j-1,memo)+2;
        else
            memo[i][j] = Math.max(rec(s,i+1,j,memo),rec(s,i,j-1,memo));
        return memo[i][j];
    }
}