【区间dp-回文子序列-7】leet 516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

分析： dp[l][r]是在[l,r]区间上的题目要求的答案--“最长回文子序列的长度”，则可以推出有以下dp公式：

dp[l][r]=(l+1==r?0:dp[l+1][r-1] )+2 条件： s[l]=s[r]

dp[l][r]=Math.max(dp[l+1][r],dp[l][r-1]) 条件s[l]!=s[r]

dp[l][r]=1, 最初始：l==r的时候，此时字符串只有1个字符

最后区间【0，n-1】的dp值dp[0][n-1]就是题目要求的字符串的最长回文子序列的长度

代码：

    public int longestPalindromeSubseq(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        for (int r = 0; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                if (l == r) dp[l][r] = 1;
                else {
                    if (s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1] + 2;
                    else dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }

类似题目：

【区间dp-回文子序列-8-1】leet 1312. 让字符串成为回文串的最少插入次数

【区间dp-回文子序列-8-2】添加最少的字符让字符串变为回文字符串

【区间dp-回文子序列-8-3】添加最少的字符让字符串变为回文字符串

【区间dp-回文子序列-8-4】SH10 回文数组