时间复杂度O(n2)
    空间复杂度O(n2)

    1. class Solution {
    2. public:
    3.     int longestPalindromeSubseq(string s) {
    4.         int res = 0;
    5.         vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
    6.         for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
    7.         for (int i = s.size() - 1; i >= 0; i--) {
    8.             for (int j = i + 1; j < s.size(); j++) {
    9.                 if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
    10.                 else {
    11.                     dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
    12.                 }
    13.             }
    14.         }
    15.         return dp[0][s.size()-1];
    16.     }
    17. };