LeetCode 516. Longest Palindromic Subsequence
2020-05-30 08:09:07 # leetcode # dynamic programming # string

Problem

LeetCode 516. Longest Palindromic Subsequence

1. 题目简述

找出一个字符串的最长回文子序列。例如：

Example 1:
Input:

"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".

2. 算法思路

和它相似的题目还有两道，LeetCode 5 最长回文子字符串和LeetCode 647 回文子字符串。

这里我们要注意，这里是子序列，而不是子字符串，子字符串是要求连续的，而子序列不是。

Dynamic Programming

对于求子序列的题目，而且还是最大值的，我们第一反应肯定还是DP，思路和 LeetCode 5 最长回文子字符串 不同的是，dp策略有所改变。

我们回忆一下，对于5，我们只考虑dp[i][j]的时候，如果s[i] == s[j]，需要考虑dp[i + 1][j - 1]是否是回文字符串，dp[i][j]表示i到j是否是回文子字符串；那么对于这道题来说，如果s[i] == s[j]，则需要将dp[i + 1][j - 1] + 2，其中dp[i][j]表示i到j的最长回文子序列的长度。

那么如果s[i] != s[j]时，对于5来说，dp[i][j]直接为false；而对于本题来说，是一个int值，dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。

base case的情况是dp[i][i] = 1，不需要考虑j - i之类的，因，如果对于j - i = 2的case来说，dp[i + 1][j - 1] = dp[i + 1][i + 1] = 1，可以正常计算的，不受影响；如果 j - i = 1，那么说明两个数挨着，dp[i + 1][j - 1]看似是不合法的，但实际上是0，直接加2也是OK的，所以边界情况无需再考虑。

所以递推式如下

\begin{equation}
dp[i][j] = dp[i + 1][j - 1] + 2 \text{ if } s[i] = s[j]
\end{equation}

\begin{equation}
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) \text{ if } s[i] \neq s[j]
\end{equation}

遍历顺序依旧按照自身喜好来，但是这里依然是和5做同样选择，因为递推式的前项依赖的需求。

时间复杂度为O(n ^ 2)，空间复杂度也是O(n ^ 2)

补充

这里用中心扩散法就明显行不通了，因为是非连续的，怎么扩散嘛，没辙。

3. 解法

Dynamic Programming bottom-up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int longestPalindromeSubseq(String s) {
        if (s.length() <= 1) {
            return s.length();
        }

        int length = s.length(), longest = 1;
        int[][] dp = new int[length][length];

        for (int i = length - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < length; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                    longest = Math.max(longest, dp[i][j]);
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return longest;
    }
}
Prev
2020-05-30 08:09:07 # leetcode # dynamic programming # string
Next