题解 | 最长回文子序列

class Solution {
  public:
    /*
        子序列：不是连续的；子串：连续的
        同样都用dp[i][j]分别表示s[i]到s[j]的最长的回文子序列长度（int）、是否是回文子串（bool）
        在子序列中：
        （2）dp[i][i]=1
        （3）dp[i][j]=0(j<i)
        （4）dp[i][j]=dp[i+1][j-1]+2 (if s[i]==s[j])
        （5）dp[i][j]=max(dp[i+1,j],dp[i,j-1]) (if s[i]!=s[j])
     */
    int longestPalindromeSubSeq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = n - 1; i >= 0; i--) {
            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];
    }
};