Count Different Palindromic Subsequences LeetCode solution in C++

1
class Solution {
2
 public:
3
  int countPalindromicSubsequences(string s) {
4
    int n = s.size();
5
    long dp[n + 1][n + 1];
6
    memset(dp, 0, sizeof dp);
7
    long MOD = 1e9 + 7;
8
    for (int i = n - 1; i >= 0; i--) {
9
      dp[i][i] = 1;
10
      for (int j = i + 1; j < n; j++) {
11
        if (s[i] != s[j])
12
          dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
13
        else {
14
          dp[i][j] = dp[i + 1][j - 1] * 2;
15
          int left = i + 1, right = j - 1;
16
          while (left <= right && s[left] != s[i]) left++;
17
          while (left <= right && s[right] != s[i]) right--;
18
          if (left > right)
19
            dp[i][j] += 2;
20
          else if (left == right)
21
            dp[i][j] += 1;
22
          else
23
            dp[i][j] -= dp[left + 1][right - 1];
24
        }
25
        dp[i][j] = (dp[i][j] + MOD) % MOD;
26
      }
27
    }
28
    return (int)dp[0][n - 1];
29
  }
30
};