Longest Palindromic Subsequence II

和 https://leetcode.com/problems/longest-palindromic-subsequence/ 的区别是, 不能连续的两个字符相连, 并且规定只能是偶数.

因为只能是偶数, 所以改动是: 1. if(i >= j) return 0; 2. 转换方程要判断是否和前一个字符相同, 所以要记录一下前边每个状态下的当前字符, 所以变成了3维dp.

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

        return memo[i][j][c];
    }
}