最长回文子序列算法详解编程语言

class Solution { 
public: 
    int longestPalindromeSubseq(string s) { 
        int n=s.size(); 
        vector<vector<int>>dp(n,vector<int>(n,0)); 
        //然后注意遍历顺序，i 从最后一个字符开始往前遍历，j 从 i + 1 开始往后遍历，这样可以保证每个子问题都已经算好了。 
        for(int i=n-1;i>=0;i--) 
        { 
            //每个数自己最小是1 
            dp[i][i]=1; 
            for(int j=i+1;j<n;j++) 
            { 
                if(s[i]==s[j]) 
                { 
                    dp[i][j]=dp[i+1][j-1]+2; 
                } 
                else 
                { 
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]); 
                } 
            } 
        } 
        return dp[0][n-1]; 
    } 
};