力扣730-统计不同回文子序列

摘要: 不同的回文子序列个数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们看一个比较难的问题，算法的核心是动态规划，根据动态规划阶段的不同选取方式，有普通的区间DP，以及序列自动机两种做法。力扣940-不同的子序列 是另一个与本体非常类似的问题。

题目

• 730. 统计不同回文子序列

给你一个字符串 s ，返回 s 中不同的非空回文子序列个数 。由于答案可能很大，请返回对 1e9 + 7 取余 的结果。

字符串的子序列可以经由字符串删除 0 个或多个字符获得。

如果一个序列与它反转后的序列一致，那么它是回文序列。

如果存在某个 i , 满足 ai != bi ，则两个序列 a1, a2, … 和 b1, b2, … 不同。

提示：

1 <= s.length <= 1000
s[i] 仅包含 'a', 'b', 'c' 或 'd'

示例 1：
输入：s = ‘bccb’
输出：6
解释：6 个不同的非空回文子字符序列分别为：’b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’。
注意：’bcb’ 虽然出现两次但仅计数一次。

示例 2：
输入：s = ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 是对 1e9 + 7 取余后的值。

题解

算法1：区间DP

定义 dp[i][j] 为 s[i..j] 上的不同回文子序列个数。于是有 dp[i][i] = 0、以及 i > j 时 dp[i][j] = 0。dp[0][n-1] 即为我们要求的。

下面我们看一下 dp[i][j] 的状态转移方程是什么。

首先是相对比较简单的 s[i] != s[j] 的情况，由容斥原理，有：

dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]

下面看比较复杂的 s[i] = s[j] = b 的情况。首先 s[i+1..j-1] 上的每一个回文子序列，在两端分别加上 b，仍然构成回文子序列。此外 b 和 bb 这两个也是回文子序列，因此：

dp[i][j] = 2 * dp[i + 1][j - 1] + 2

但是其中可能有重复的情况计数的情况。也就是 s[i+1..j-1] 中可能有 b 的情况。我们要分两种情况考虑：

(1) s[i+1..j-1] 中含有 1 个 b

比如 s[i..j] = bcbcb，此时子问题 s[i+1..j-1] = cbc 含 1 个 b。于是单独的 b 作为一个回文子序列，在子问题里会被计数，那么 dp[i][j] 中就要相应减 1：

dp[i][j] = 2 * dp[i + 1][j - 1] + 1

(2) s[i+1..j-1] 中含有 2 个以上的 b

比如 s[i..j] = bcbcbabcb，于是 s[i+1..j-1] = cbcbabc，里面含有两个以上 b，取最左边的和最右边的 b，对应的区间记为 [l, r]，于是 s[l..r] = bcbab，s[l..r] 的子问题 s[l+1..r-1] = cba 中所有的回文子序列，在计算 dp[l][r] 时都会在两端加上 b 计数一次，而这就是与 dp[i][j] 重复计数的部分。因此：

dp[i][j] = dp[i+1][j-1] * 2 - dp[l + 1][r - 1]

综上，区间 DP 算法如下：

状态定义：
dp[i][j] := 在 s[i..j] 上的不同回文子序列个数

初始化：
dp[i][j] = 0   j < i 
dp[i][i] = 1 

答案：
dp[0][n - 1]

状态转移：
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]     s[i] != s[j]
           dp[i][j] = 2 * dp[i + 1][j - 1] + 2                s[i] = s[j] = b，且 s[i+1..j-1] 中不含 b
           dp[i][j] = 2 * dp[i + 1][j - 1] + 1                s[i] = s[j] = b，且 s[i+1..j-1] 中含 1 个 b
           dp[i][j] = 2 * dp[i + 1][j - 1] - dp[l+1][r-1]     s[i] = s[j] = b，且 s[i+1..j-1] 中含 两个以上 b

代码 (C++)

class Solution {
public:
    int countPalindromicSubsequences(string S) {
        if(S.empty()) 
            return 0;
        int n = S.size();
        if(n == 1) 
            return 1;

        vector<vector<int> > dp(n, vector<int>(n, 0));
        for(int i = 0; i < n ; ++i)
            dp[i][i] = 1;

        for(int j = 1; j < n; ++j)
            for(int i = j - 1; i >= 0; --i)
            {
                if(S[i] != S[j])
                    dp[i][j] = dp[i][j - 1] - dp[i + 1][j - 1] + dp[i + 1][j];
                else
                {
                    int l = i + 1, r = j - 1;
                    while(l <= r && S[i] != S[l]) 
                        ++l;
                    while(l <= r && S[i] != S[r]) 
                        --r;
                    if(l > r)
                        dp[i][j] = 2 * dp[i + 1][j - 1] + 2;
                    else if(l == r)
                        dp[i][j] = 2 * dp[i + 1][j - 1] + 1;
                    else
                        dp[i][j] = 2 * dp[i + 1][j - 1] - dp[l + 1][r - 1];
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD;
            }
        return dp[0][n - 1];
    }

private:
    static constexpr long MOD = 1000000007;
};

算法2：序列自动机

将原字符串 $s$ 与其反串 $s’$ 分别建立序列自动机 seq_am1 和 seq_am2。原串的回文子序列可以转化为 $s$ 和 $s’$ 的公共子序列。

因此我们可以通过考察 $s$ 个 $s’$ 的公共子序列个数来计算原串回文子序列个数，定义以下状态：

dp[i][j] := 从两个序列自动机的状态组 (i, j) 出发，可以取到的回文子序列个数，含空子序列

如果找到了可以转移的字符 ch，也就是 nxt_i, nxt_j 均不为 -1。在转移到 (nxt_i, nxt_j) 之前需要注意两个地方：

(1) 构造出的原和反串本质上是一个串，$s’$ 上从左往右走相当于 $s$ 上从右往左走。需要注意长度的问题。
(2) 转移到 (nxt_i, nxt_j) 之后算的都是两个 ch 中间夹一部分的情况，而单取一个 ch 会形成奇数长度的回文子序列，这需要单独计算进去。

• nxt_i + nxt_j > n + 1 时长度就超了，因此 ch 对 dp[i][j] 没贡献。
• nxt_i + nxt_j <= n + 1 时，可以单取一个 ch，形成奇数子序列。
• nxt_i + nxt_j < n + 1 时，可以转移至 (nxt_i, nxt_j)。

代码 (C++)

using ll = long long;
const int MOD = 1e9 + 7;

class SeqAM
{
public:
    SeqAM(){}
    SeqAM(const string& t)
    {
        build(t);
    }

    void build(const string& t)
    {
        // 由字符串 t 建立序列自动机
        int n = t.size(); 
        int m = 4; // 字母表中的字符数
        nxt.assign(n + 1, vector<int>(m, -1)); // 状态节点 0 ~ n，字母表 0 ~ m-1
        
        for(int i = n - 1; i >= 0; --i)
        {
            for(int ch = 0; ch < 4; ++ch)
                nxt[i][ch] = nxt[i + 1][ch];
            nxt[i][t[i] - 'a'] = i + 1; 
        }
    }

    bool find(const string& s) const
    {
        int l = s.size();
        int p = 0; // 初始状态
        for(int i = 0; i < l; ++i)
        {
            p = nxt[p][s[i] - 'a'];
            if(p == -1)
                return false;
        }
        return true;
    }

    int check_nxt(int i, int ch) const
    {
        return nxt[i][ch];
    }

private:
    vector<vector<int>> nxt;
};

int dfs(int i, int j, vector<vector<int>>& dp, const SeqAM& seq_am1, const SeqAM& seq_am2, const int n)
{
    if(dp[i][j] != -1)
        return dp[i][j];

    dp[i][j] = 0;

    for(int ch = 0; ch < 4; ++ch)
    {
        int nxt_i = seq_am1.check_nxt(i, ch);
        int nxt_j = seq_am2.check_nxt(j, ch);
        if(nxt_i != -1 && nxt_j != -1)
        {
            if(nxt_i + nxt_j > n + 1)
                continue;
            if(nxt_i + nxt_j < n + 1) // 偶数子序列
                dp[i][j] = ((ll)dp[i][j] + dfs(nxt_i, nxt_j, dp, seq_am1, seq_am2, n)) % MOD;
            // 奇数子序列
            dp[i][j] = ((ll)dp[i][j] + 1) % MOD;
        }
    }
    // 空子序列
    dp[i][j] = ((ll)dp[i][j] + 1) % MOD;
    return dp[i][j];
}

class Solution {
public:
    int countPalindromicSubsequences(string S) {
        if(S.empty()) 
            return 0;
        int n = S.size();
        if(n == 1) 
            return 1;

        SeqAM seq_am1(S);
        reverse(S.begin(), S.end());
        SeqAM seq_am2(S);
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));

        return ((ll)dfs(0, 0, dp, seq_am1, seq_am2, n) - 1 + MOD) % MOD;
    }
};

---