message: Update count-different-palindromic-subsequences.cpp
diff: // Time: O(n^2)
  // Space: O(n)
  -
  class Solution {
  public:
  int countPalindromicSubsequences(string S) {
  @@ -38,3 +37,53 @@ public:
  return result;
  }
  };
  +
  +// Time: O(n^2)
  +// Space: O(n^2)
  +class Solution2 {
  +public:
  + int countPalindromicSubsequences(string S) {
  + vector<vector<int>> prv(S.length(), vector<int>(4, -1));
  + vector<vector<int>> nxt(S.length(), vector<int>(4, -1));
  + vector<int> last(4, -1);
  + for (int i = 0; i < S.length(); ++i) {
  + last[S[i] - 'a'] = i;
  + prv[i] = last;
  + }
  + last = vector<int>(4, -1);
  + for (int i = S.length() - 1; i >= 0; --i) {
  + last[S[i] - 'a'] = i;
  + nxt[i] = last;
  + }
  + vector<vector<int>> lookup(S.length(), vector<int>(S.length(), -1));
  + return dp(0, S.length() - 1, prv, nxt, &lookup) - 1;
  + }
  +
  +private:
  + int dp(const int i, const int j,
  + const vector<vector<int>>& prv,
  + const vector<vector<int>>& nxt,
  + vector<vector<int>> *lookup) {
  +
  + if ((*lookup)[i][j] != -1) {
  + return (*lookup)[i][j];
  + }
  + auto result = 1;
  + if (i <= j) {
  + for (int x = 0; x < 4; ++x) {
  + auto i0 = nxt[i][x];
  + auto j0 = prv[j][x];
  + if (i <= i0 && i0 <= j) {
  + result = (result + 1) % P;
  + }
  + if (i0 != -1 && j0 != -1 && i0 < j0) {
  + result = (result + dp(i0 + 1, j0 - 1, prv, nxt, lookup)) % P;
  + }
  + }
  + }
  + result %= P;
  + (*lookup)[i][j] = result;
  + return result;
  + }
  + static const int P = 1e9 + 7;
  +};
  