题解 | #最长回文子序列# 动态规划需要单独出一个专题了。

/*
dp(i,j)表示从 i-j的最长的回文子串的长度
i 从len-1 到 0
j 从 i+1 到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));
}
*/
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        int len = s.size();
        vector<vector<int>> dp(len, vector<int>(len, 0));
        // dp(i,j)表示从i到j的最长回文子串长度。
        // 初始化
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < len; 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][len-1];
        
        
    }
};