【区间DP】【hard】力扣730. 统计不同回文子序列

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

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

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

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

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

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

提示：
1 <= s.length <= 1000
s[i] 仅包含 ‘a’, ‘b’, ‘c’ 或 ‘d’

三维DP

class Solution {
public:
    int countPalindromicSubsequences(string s) {
        int MOD = 1e9 + 7;
        int n = s.size();
        vector<vector<vector<int>>> dp(4, vector<vector<int>>(n, vector<int>(n, 0)));
        for(int i = 0; i < n; i++){
            dp[s[i] - 'a'][i][i] = 1; 
        }

        for(int len = 2; len <= n; len++){
            for(int i = 0, j = len - 1; j < n; i++, j++){
                for(char c = 'a'; c <= 'd'; c++){
                    char k = c - 'a';
                    if(s[i] == c && s[j] == c){
                        dp[k][i][j] = (2LL + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]) % MOD;
                    }
                    else if(s[i] == c){
                        dp[k][i][j] = dp[k][i][j-1];
                    }
                    else if(s[j] == c){
                        dp[k][i][j] = dp[k][i+1][j];
                    }
                    else{
                        dp[k][i][j] = dp[k][i+1][j-1];
                    }
                }
            }
        }
        
        int res = 0;
        for(int k = 0; k < 4; k++){
            res = (res + dp[k][0][n-1]) % MOD;
        }
        return res;
    }
};

我们定义一个三维数组dp[k][i][j]来表示在i到j范围内并且以k开头的回文子序列的总数。我们在状态转移过程中，可以先不断遍历i和j之间的范围len，那么我们接下来继续遍历i的时候，j实际上也会知道，最后在最里层循环中遍历k是多少。

当s[I] = s[j]的时候，那么i+1到j-1中的回文子序列加上两边的x都是以x为开头的回文子序列，并且字符c可以构成c或者cc两个回文子序列，所以有状态转移方程dp[k][i][j] = (2LL + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]) % MOD;。

首尾字符中只有 s[i] 是我们感兴趣的字符 c。
因此，当前子串 s[i…j] 中以 c 为边界的回文子序列，与子串 s[i…j-1] 中以 c 为边界的回文子序列是相同的，因为 s[j] 不会对结果产生影响。

接下来的几种情况同理。

最后我们定义一个变量res来记录以不同字符开头的长度为n的字符串的回文子序列总数。