516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

1
2
3
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

1
2
3
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

区间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) {
        char cs[] = s.toCharArray();
        int n = cs.length;
        int memo[][] = new int[n][n];
        for (int m[] : memo) Arrays.fill(m, -1);
        return dfs(cs, 0, n-1, memo);
    }
    private int dfs(char cs[], int i, int j, int memo[][]) {
        if (i > j) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int res = Math.max(dfs(cs, i+1, j, memo), dfs(cs, i, j-1, memo));
        if (cs[i] == cs[j]) {
            res = Math.max(res, dfs(cs, i+1, j-1, memo) + (i == j ? 1 : 2));
        }
        return memo[i][j] = res;
    }
}

区间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) {
        char cs[] = s.toCharArray();
        int n = cs.length;
        // f[i][j]: 字符串s[i-1:j-1]的最长回文子序列长度
        int f[][] = new int[n+2][n+2];
        for (int i = n-1; i >= 0; i--) {  // 要计算f[i][j]，必须先把f[i+1][⋅]算出来，那么只有i从大到小枚举才能做到
            for (int j = i; j < n; j++) {  // 对于j，要计算f[i][j]，必须先把f[i][j−1]算出来，所以j必须从小到大枚举
                f[i+1][j+1] = Math.max(f[i+1][j+1], f[i+2][j+1]);
                f[i+1][j+1] = Math.max(f[i+1][j+1], f[i+1][j]);
                if (cs[i] == cs[j]) {
                    f[i+1][j+1] = Math.max(f[i+1][j+1], f[i+2][j] + (i==j ? 1 : 2));
                }
            }
        }
        return f[1][n];
    }
}

区间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) {
        char cs[] = s.toCharArray();
        int n = cs.length;
        // f[i][j]: 字符串s[i:j]的最长回文子序列长度
        int f[][] = new int[n][n];
        for (int i = n-1; i >= 0; i--) {  // 要计算f[i][j]，必须先把f[i+1][⋅]算出来，那么只有i从大到小枚举才能做到
            f[i][i] = 1;
            for (int j = i+1; j < n; j++) {  // 在计算f[i][j]的时候，必须先把f[i][j−1]算出来，所以j必须从小到大枚举
                f[i][j] = Math.max(f[i+1][j], f[i][j-1]);
                if (cs[i] == cs[j]) {
                    f[i][j] = Math.max(f[i][j], f[i+1][j-1] + (i==j ? 1 : 2));
                }
            }
        }
        return f[0][n-1];
    }
}