516. Longest Palindromic Subsequence.md

516. Longest Palindromic Subsequence

https://leetcode.com/problems/longest-palindromic-subsequence/

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: Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is "bbbb".

Example 2: Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is "bb".

思路

• DP，dp[i][j] 表示string中从index[i...j] 之间存在的回文子序列个数（子问题的解），最后返回的结果为dp[0][n-1]。

• pattern 1：string = "a.....a"，即s[i] = s[j]，则 dp[i][j] = dp[i+1][j-1] + 2，表示两个“a”中间的回文序列个数（子问题的解）加上前后两个"a"的长度。

• pattern 2：string = "a.....b"，即s[i] != s[j]，则 dp[i][j] = max(dp[i+1][j] , dp[i][j-1])，表示除“a”以外的右半部分的解，和除"b"以外左半部分的解里面，取最大值。

代码

class Solution {
    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0)
            return 0;
        char[] A = s.toCharArray();
        int n = A.length;
        int[][] dp = new int[n][n];
        
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (i == j) {
                    dp[i][j] = 1;
                    continue;
                }
                if (A[i] == A[j]) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
                else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
}