动态规划+容斥原理：求解《730. 统计不同回文子序列》

例题

730. 统计不同回文子序列

给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。
通过从 s 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。
如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。
注意：
结果可能很大，你需要对 109 + 7 取模 。 示例 1：
输入：s = 'bccb'
输出：6
解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。

答案

动态规划

var countPalindromicSubsequences = function(s) {
  const n = s.length, MOD = 10 ** 9 + 7
  const dp = Array.from({length: 4}, _ => Array.from({length: n}, _ => new Uint32Array(n)))
  for (let i = 0; i < n; i++) dp[s.charCodeAt(i) - 97][i][i] = 1
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      const j = i + len - 1, a = s.charCodeAt(i) - 97, b = s.charCodeAt(j) - 97
      for (let k = 0; k < 4; k++) {
        if (a === k && b === k) {
          dp[k][i][j] = (2 + (dp[0][i + 1][j - 1] + dp[1][i + 1][j - 1]) % MOD + (dp[2][i + 1][j - 1] + dp[3][i + 1][j - 1]) % MOD) % MOD
        } else if (a === k) {
          dp[k][i][j] = dp[k][i][j - 1]
        } else if (b === k) {
          dp[k][i][j] = dp[k][i + 1][j]
        } else {
          dp[k][i][j] = dp[k][i + 1][j - 1]
        }
      }
    }
  }
  let sum = 0
  for (let k = 0; k < 4; k++) sum = (sum + dp[k][0][n - 1]) % MOD
  return sum
};

容斥原理

function countPalindromicSubsequences(s: string): number {
  const n = s.length
  const dp = Array.from({length: n}, _ => new Int32Array(n))
  const MOD = 1e9 + 7
  for (let i = 0; i < n; i++) dp[i][i] = 1
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      const j = i + len - 1
      if (s[i] !== s[j]) dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]
      else {
        dp[i][j] = 2 + dp[i + 1][j - 1] * 2
        let l = i + 1, r = j - 1
        while (l <= r && s[l] !== s[i]) l++
        while (l <= r && s[r] !== s[i]) r--
        if (l === r) dp[i][j]-- // 1 个相同
        if (l < r) dp[i][j] -= dp[l + 1][r - 1] + 2 // >= 2 个相同
      } 
      dp[i][j] = dp[i][j] < 0 ? dp[i][j] + MOD : dp[i][j] % MOD
    }
  }
  return dp[0][n - 1]
};