Longest Palindromic Subsequence II
和 https://leetcode.com/problems/longest-palindromic-subsequence/ 的区别是, 不能连续的两个字符相连, 并且规定只能是偶数.
因为只能是偶数, 所以改动是: 1. if(i >= j) return 0; 2. 转换方程要判断是否和前一个字符相同, 所以要记录一下前边每个状态下的当前字符, 所以变成了3维dp.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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]; } } |