LeetCode 题解-516.longest-palindromic-subsequence

对Leetcode 516.longest-palindromic-subsequence 题目的求解。

Problem Description#

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1#

1
Input:
2
"bbbab"
3
Output:
4
4

Example 2#

1
Input:
2

3
"cbbd"
4
Output:
5
2

Analysis#

这道题目和第5题类似，不过第五题中我们考虑的时候包含区间头尾的回文串，而在这道题目中，我们需要考虑区间内的最长回文串，是一道很明显的动态规划题目，递归公式为

1
dp[i][j] = max(dp[i+1][j], dp[i][j-1]) if s[i] neq s[j]
2
dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]+2) if s[i] eq s[j]

Solution 1: bfs with recursive call#

1
class Solution {
2
    public static int longestPalindromeSubseq(String s) {
3
        int l = s.length();
4
        if (l == 0) return 0;
5
        int dp[][] = new int [l][l];
6
        //int start = 0;
7
        for (int i = l-1; i >= 0; --i){
8
            for (int j = i; j < l ; ++j){
9
                //System.out.printf("%d %d\n", i, j);
10
                if (i == j) dp[i][j] = 1;
11
                //dp[i][j] = Math.max(dp[i][i+len-2], dp[i+1][i+len]);
12
                else if (s.charAt(i) == s.charAt(j)){
13
                    dp[i][j] = dp[i+1][j-1]+2;
14
                }
15
                else dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
16
            }
17
        }
18
        return dp[0][l-1];
19

20
    }
21
}