730 统计不同回文子序列（区间dp）

た入场券 2022-09-10 00:20 105阅读 0赞

**1. 问题描述：**

给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10 ^ 9 + 7 的模。通过从 S 中删除 0 个或多个字符来获得子序列。如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。如果对于某个 i，A\_i != B\_i，那么 A\_1, A\_2, ... 和 B\_1, B\_2, ... 这两个字符序列是不同的。

**示例 1：**

输入：  
S = 'bccb'  
输出：6

**解释：**

6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。  
注意：'bcb' 虽然出现两次但仅计数一次。

**示例 2：**

输入：  
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'  
输出：104860361

**解释：**

共有 3104860382 个不同的非空回文子序列，对 10 ^ 9 + 7 取模为 104860361。

**提示：**

字符串 S 的长度将在\[1, 1000\]范围内。  
每个字符 S\[i\] 将会是集合 \{'a', 'b', 'c', 'd'\} 中的某一个。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/count-different-palindromic-subsequences

**2. 思路分析：**

这道题目属于经典的dp问题，分析题目可以知道只有当子序列对应的值不同才应该被计算为不同的回文串，当位置不同但是对应的子序列相同的时候属于同一种子序列，而这道题目计算的是不同子序列的数目，这是我们在考虑状态计算的时候需要注意的问题。对于动态规划的题目我们我们需要考虑两个方面：① 状态表示 ② 状态计算；我们可以定义一个二维数组或者列表，其中dp\[i\]\[j\]表示区间\[i，j\]不同回文子序列的数量；怎么样进行状态计算呢？状态计算对应集合的划分，因为只有当子序列不同那么才应该计算为不同的回文串，因为只有a，b，c，d四种字符，所以我们可以集合划分为四大类：对应子序列最外侧的字母分别为a，b，c，d，也即a...a，b...b，c...c，d...d，当我们选择的最外侧里面的两个字符的时候可以将他们换成是最外侧的两个相同的字符，替换前与替换后不影响结果，将集合划分为四大类之后我们求解出每一类的值相加起来就是当前整个集合的值：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_10_color_FFFFFF_t_70_g_se_x_16][]

这里初始化空串也为回文串的一个好处是能够将最外侧回文串的情况计算为最外层里面的空串的情况，例如a....a中最外侧的子序列aa也属于回文串而dp\[l + 1，r - 1\]计算的时候将空串的情况也计算在里面了，所以这两者可以看做是相互抵消了，所以最终不同的回文子串计算多了一次所以需要减去1，这里还存在一个问题是如何快速求解出最外侧的相同字母的位置，对于python语言我们可以声明长度为4并且每一个长度都为列表的嵌套列表来存储相同字母出现的位置（只有四种字母所以长度为4），我们可以对列表中第一个元素和最后一个元素操作，我们可以在遍历的时候维护这个列表，类似于滑动窗口当窗口的左边界小于当前的区间左端点的时候那么弹出当前字母对应位置的最左边的元素即可。对于c++语言可以声明一个双端队列，双端队列也支持对第一个元素和最后一个元素进行操作。

**3. 代码如下：**

**python：**

class Solution:
        def countPalindromicSubsequences(self, s: str) -> int:
            n = len(s)
            MOD = 10 ** 9 + 7
            # 空串也属于回文串所以初始化的时候应该令其为l
            dp = [[1] * (n + 2) for i in range(n + 2)]
            # 长度为1的字符也属于回文串
            for i in range(1, n + 1): dp[i][i] += 1
            # 最外层的循环表示区间的长度为l
            for l in range(2, n + 1):
                # 声明长度为4的列表, 其中q[i]又是一个列表, 用来添加对应的下标
                q = [list() for i in range(4)]
                for i in range(1, n + 1):
                    # 记录当前字符对应的位置, 将字母出现的位置存储到对应的位置中
                    q[ord(s[i - 1]) - ord("a")].append(i)
                    j = i - l + 1
                    if j >= 1:
                        # 四种情况分为对应a...a，b...b,c...c,d...d
                        for k in range(4):
                            while q[k] and q[k][0] < j: q[k].pop(0)
                            if q[k]:
                                # 每一次遍历的时候不同的字符中长度为1的字符也属于回文串
                                dp[j][i] += 1
                                _l, _r = q[k][0], q[k][-1]
                                if _l < _r:
                                    # 状态计算
                                    dp[j][i] = (dp[j][i] + dp[_l + 1][_r - 1]) % MOD
            return (dp[1][n] - 1 + MOD) % MOD

**c++：**

#include<vector>
    #include<deque>
    #include<string>
    #include<iostream>
    using namespace std;
    
    class Solution {
    public:
        int countPalindromicSubsequences(string s) {
            int n = s.size(), MOD = 1e9 + 7;
            vector<vector<int>> f(n + 2, vector<int>(n + 2, 1));
            for (int i = 1; i <= n; i ++ ) f[i][i] ++ ;
            for (int len = 2; len <= n; len ++ ) {
                deque<int> q[4];
                for (int i = 1; i <= n; i ++ ) {
                    q[s[i - 1] - 'a'].push_back(i);
                    int j = i - len + 1;
                    if (j >= 1) {
                        for (int k = 0; k < 4; k ++ ) {
                            while (q[k].size() && q[k].front() < j) q[k].pop_front();
                            if (q[k].size()) {
                                f[j][i] ++ ;
                                int l = q[k].front(), r = q[k].back();
                                if (l < r)
                                    f[j][i] = (f[j][i] + f[l + 1][r - 1]) % MOD;
                            }
                        }
                    }
                }
            }
            return (f[1][n] + MOD - 1) % MOD;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a5e339cf59574cfaad21b0ef57df077a.png