【算法】lc516最长回文子序列 区间dp

题目链接

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

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

经典区间dp题目
思路：集合角度解决dp问题

ac code

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for(int len = 1; len <= n; len ++){
            for(int l = 0; l + len - 1 < n; l ++){
                int r = l + len - 1;
                if(len == 1){
                    f[l][r] = 1;
                }else{
                    if(s.charAt(l) == s.charAt(r))f[l][r] = f[l + 1][r - 1] + 2;
                    f[l][r] = Math.max(f[l][r],Math.max(f[l + 1][r],f[l][r - 1 ]));
                }

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