leetcode 516-DP

• 基本思想：
  名词解释：什么是回文子序列？就是说一个字符串中可以忽略几个char但是最终还是会成为回文序列：
  例如：bbaababb:
  可以忽略这个a，这样就是一个最长的回文字符串

  
  图片.png

• 算法解释：

  
  图片.png
  

  abba:是一个标准回文 长度是4
  abbax:最后的x可以忽略 结果还是4.

C++：下面的代码是两种做法，一种是标准的dp:dp[i][j]代表从i到j最长长度
方法二：len 和dp 代表算法解释中的两种情况：

//int longestPalindromeSubseq(string s) {
//  int n = s.size();
//  vector<vector<int>> dp(n, vector<int>(n));
//  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];
//}
//faster
int longestPalindromeSubseq(string s) {
    vector<int> dp(s.size(), 1);
    int n = s.size();
    int len = 0;
    for (int i = n - 1; i >= 0; i--) {
        len = 0;
        for (int j = i + 1; j < n; j++) {
            int t = dp[j];
            if (s[i] == s[j]) {
                dp[j] = len + 2;
            }
            len = max(len, t);
        }
    }
    int ans = 0;
    for (auto aa : dp)
        ans = max(ans, aa);
    return ans;
}