关于程序员:宫水三叶的刷题日记730-统计不同回文子序列困难

这是 LeetCode 上的 730. 统计不同回文子序列 ，难度为艰难。

Tag :「区间 DP」、「动静布局」

给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数。

通过从 s 中删除 $0$ 个或多个字符来取得子序列。

如果一个字符序列与它反转后的字符序列统一，那么它是「回文字符序列」。

如果有某个 $i$ , 满足 $a_i$ != $b_i$，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。

留神：

后果可能很大，你须要对 $10^9 + 7$ 取模。

示例 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」，同时 s 仅由 $4$ 类小写字母组成，也是一个切入点。

依据区间 DP 的个别思路，定义 $f[i][j]$ 为思考字符串 s 中的 $[i,j]$ 范畴内回文子序列的个数，最终答案为 $f[0][n – 1]$。

不失一般性思考 $f[i][j]$ 该如何转移，通过枚举 abcd 作为回文计划「边缘字符」来进行统计，即别离统计各类字符作为「边缘字符」时对 $f[i][j]$ 的奉献，此类统计形式天生不存在重复性问题。

假如以后枚举到的字符为 $k$：

若 $s[i…j]$ 中没有字符 $k$，则字符 $k$ 对 $f[i][j]$ 奉献为 $0$，跳过；
若 $s[i…j]$ 中存在字符 $k$，依据字符 $k$ 在范畴 $s[i…j]$ 中「最小下标」和「最大下标」进行分状况探讨，假如字符 $k$ 在 $s[i…j]$ 中「最靠左」的地位为 $l$，「最靠右」的地位为 $r$：
- 当 $l = r$ 时，此时字符 $k$ 对 $f[i][j]$ 的奉献为 $1$，即 k 自身；
- 当 $l = r – 1$ 时，阐明字符 $k$ 两头不存在任何字符，此时字符 $k$ 对 $f[i][j]$ 的奉献为 $2$，包含 k 和 kk 两种回文计划；
- 其余状况，可依据已算得的「小区间回文计划」进行延长（两段别离补充位于 $l$ 和 $r$ 的字符 $k$），失去新的大区间计划，此局部对 $f[i][j]$ 的奉献是 $f[l + 1][r – 1]$，另外还有 k 和 kk 两种回文计划，因而总的对答案的奉献为 $f[l + 1][r – 1] + 2$。

统计 $s[i…j]$ 中各类字符「最靠左」和「最靠右」的地位，可通过调整枚举方向来实现：从大到小枚举 $i$，同时保护 L[s[i]-'a'] = i，即可失去「最靠左」的地位；在确定左端点 $i$ 之后，从小达到枚举右端点 $j$，同时保护 R[s[i]-'a'] = j，即可失去「最靠右」的地位。

代码：

class Solution {int MOD = (int)1e9+7;
    public int countPalindromicSubsequences(String s) {char[] cs = s.toCharArray();
        int n = cs.length;
        int[][] f = new int[n][n];
        int[] L = new int[4], R = new int[4];
        Arrays.fill(L, -1);
        for (int i = n - 1; i >= 0; i--) {L[cs[i] - 'a'] = i;
            Arrays.fill(R, -1);
            for (int j = i; j < n; j++) {R[cs[j] - 'a'] = j;
                for (int k = 0; k < 4; k++) {if (L[k] == -1 || R[k] == -1) continue;
                    int l = L[k], r = R[k];
                    if (l == r) f[i][j] = (f[i][j] + 1) % MOD;
                    else if (l == r - 1) f[i][j] = (f[i][j] + 2) % MOD;
                    else f[i][j] = (f[i][j] + f[l + 1][r - 1] + 2) % MOD;
                }
            }
        }
        return f[0][n - 1];
    }
}

工夫复杂度：$O(C \times n^2)$，其中 $C = 4$ 为字符集大小
空间复杂度：$O(n^2)$

这是咱们「刷穿 LeetCode」系列文章的第 No.730 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

本文由 mdnice 多平台公布

关于程序员:宫水三叶的刷题日记730-统计不同回文子序列困难

题目形容

区间 DP

最初