JZTXT

LeetCode 516. 最长回文子序列

发布时间 2023-05-07 20:07:45作者: 穿过雾的阴霾
class Solution {
public:
    int f[1010][1010];//f[i][j]表示s[i~j]之间的最长序列
    int INF=0x3f3f3f3f;
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        s=' '+s;
        for(int len=1;len<=n;len++)
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                if(len==1)    f[i][j]=1;
                else
                {
                    f[i][j]=max(f[i+1][j],f[i][j-1]);
                    if(s[i]==s[j])
                        f[i][j]=max(f[i][j],f[i+1][j-1]+2);
                }
                
            }
        return f[1][n];
    }
};