leetcode516最长回文子序列（dp）

发表于 | 分类于

题目

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1

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

示例 2

1
2
3
输入:"cbbd"
输出:2
一个可能的最长回文子序列为 "bb"。

题解

这是一道动态规划的题，要注意他和上一篇求最长回文子串的区别。

我们用dp[i][j]表示从i到j子串的最长回文子序列。
例如：

index：01234
s = “bbbab”

Base case:

dp[i][i-1]=0(size=0)
dp[i][i] = 1(size=1)

规则推导：

size=2

dp[0][1] = 2
dp[1][2] = 2
dp[2][3] = max(dp[2][2],dp[3][3])=1
dp[3][4] = max(dp[3][3],dp[4][4])=1

size = 3

dp[0][2] = 2+M[1][1] = 3
dp[1][3] = max(dp[1][2],dp[2][3])=2
dp[2][4] = 2+dp[3][3] = 3

一般化：

Case1:if s[i]==s[j],dp[i][j] = 2+dp[i+1][j-1]

Case2:if s[i]!=s[j],dp[i][j] = max(dp[i+1][j],dp[i][j-1])

从状态转移方程可以看出，计算dp[i][j]时需要用到dp[i+1][j - 1]和dp[i + 1][j]，所以对于i的遍历应该从尾部开始，最后返回dp[0][s.length() - 1]就行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        
        for (int i = s.length() - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
}