题解 |动态规划解最长回文子序列

1.想想与回文 子串 有什么区别（子串与子序列）
2.初始条件
3.循环遍历从后开始。
class Solution {
public:
    int longestPalindromeSubSeq(string s) {
        int n = s.size();

        //dp[i][j],从下标 i 到下标 j 的子串中，回文子序列的最大长度
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i = 0; i < n; i++)
            dp[i][i] = 1;

        //从后往前遍历，子问题以被计算
        for(int i = n-1; i >= 0; i--){
            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];
    }
};