https://leetcode.cn/problems/longest-palindromic-subsequence/submissions/577570212/

性质1：对于字符a，把a反过来赋值给b，求a的最长回文子序列就是求a和b的最长公共子序列

设dp[l][r]代表l到r的最长回文子序列

情况1：l和r都不取，dp[l][r]=max(dp[l][r],dp[l+1][[r-1])

情况2：l+1,r

情况3：l，r-1

情况4：s[l]和s[r]相等，必定是dp[l+1][-1]+2最优

画出dp表：

l和r相等时，dp[l][r]=1,l+1==r时，如果s[l]==s[r]，dp[l][r]=2,否则为1,就以此为基础展开dp表，答案就是dp[0][n-1]

const int N=1010;
int dp[N][N];
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.length();
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                dp[i][j]=0;
        for(int i=0;i<n;i++) dp[i][i]=1;
        for(int l=n-1;l>=0;l--)
        {
            for(int r=l+1;r<n;r++)
            {
                if(l+1==r)
                {
                    if(s[l]==s[r]) dp[l][r]=2;
                    else dp[l][r]=1;
                }
                else
                {
                    if(s[l]==s[r]) dp[l][r]=max(dp[l][r],dp[l+1][r-1]+2);
                    else dp[l][r]=max(dp[l+1][r],dp[l][r-1]);
                }
            }
        }
        return dp[0][n-1];
    }
};