2021-02-02 之 516. 最长回文子序列

题目地址(516. 最长回文子序列)

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

题目描述

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

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

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

提示：
1 <= s.length <= 1000
s 只包含小写英文字母

思路

假设dp[i][j]为i到j的最长子序列，当i=j时，单个字符，最长回文子序列就是他自己，为1.
先往两边扩展，可以就直接拓展2个，不行就看往左拓展回文子序列长还是往右拓展一个字符子序列长。
如果s[i]==s[j]，说明当前两个字符可以纳入回文子序列，此时dp[i][j]=dp[i+1][j-1]+2, (前一个状态dp[i+1][j-1]直接拓展两个长度)这是从最右边逐个字符往两边拓展。
如果s[i]!=s[j]，dp[i][j] = Max(dp[i+1][j], dp[i][j-1])，s[i]和sj对构成回文子序列没用，i到j的最长回文子序列就为，前一个状态s[i+1][j-1]向右拓展一个字符或向左拓展一个字符的回文子序列的最大值。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/2 11:22 下午
 */
public class LongestSubSquence {
    public static void main(String[] args) {
        String s = "bbbab";
        int len = getLongestSubSquence(s);
        System.out.println(len);
    }

    private static int getLongestSubSquence(String s) {
        if (s == null || s.length() <= 2) {
            return s.length();
        }

        int[][] dp = new int[s.length()][s.length()];
        for (int i=0; i<dp.length; i++) {
            dp[i][i] = 1;
        }
        for (int i=s.length() - 1; i >= 0; i--) {
            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];
    }
}