题目地址：
https://leetcode.com/problems/count-different-palindromic-subsequences/
给定一个长 n n n的字符串 s s s，求其所有不同的非空的回文子序列的个数。两个子序列不同当且仅当它们的字母构成不同（或者字母不同，或者某个字母个数不同）。
思路是动态规划。设 f [ i ] [ j ] f[i][j] f[i][j]是 s [ i : j ] s[i:j] s[i:j]包含多少个回文子序列。注意这里需要包含空序列，因为空序列也是回文的，方便代码的书写。那么所有的回文子序列可以按照以谁开头以谁结尾来分类，由于字母总共只有四种，所以要么以
'a'
开头结尾，要么以
'b'
或
'c'
或
'd'
开头结尾。这四种情况是不相交的，并且构成了所有情况，所以我们只需要考虑以
'a'
开头结尾的情形怎么求。不妨设 g [ i ] [ j ] g[i][j] g[i][j]是 s [ i : j ] s[i:j] s[i:j]中以
'a'
开头结尾的不同回文子序列的个数，那么我们先找到这个区间里最左和最右边的
'a'
的下标，比如说是 l l l和 r r r，我们断言，在 l ≠ r l\ne r l=r的情况下， g [ i ] [ j ] = g [ l + 1 ] [ r − 1 ] + 1 g[i][j]=g[l+1][r-1]+1 g[i][j]=g[l+1][r−1]+1（当然如果这个区间里不存在字母
'a'
的话 g [ i ] [ j ] = 0 g[i][j]=0 g[i][j]=0，如果只存在 1 1 1个
'a'
的话 g [ i ] [ j ] = 1 g[i][j]=1 g[i][j]=1，这两个情况我们要特判）。首先，对于任意 s [ i : j ] s[i:j] s[i:j]中以
'a'
开头结尾的回文子序列，可以将两个
'a'
取成 s [ l ] s[l] s[l]和 s [ r ] s[r] s[r]，剩余部分是 s [ l + 1 : r − 1 ] s[l+1:r-1] s[l+1:r−1]的回文子序列，所以每个以
'a'
开头结尾的回文子序列都对应一个 s [ l + 1 : r − 1 ] s[l+1:r-1] s[l+1:r−1]的回文子序列，并且这是单射；反之，对于任意一个 s [ l + 1 : r − 1 ] s[l+1:r-1] s[l+1:r−1]的回文子序列，两边加上 s [ l ] s[l] s[l]和 s [ r ] s[r] s[r]，就对应着 s [ i : j ] s[i:j] s[i:j]的以
'a'
开头结尾的回文子序列，所以是满射。所以这个映射是一一对应的。另外再加上单独由一个
'a'
组成的回文子序列，所以有： g [ i ] [ j ] = { g [ l + 1 ] [ r − 1 ] + 1 , l < r − 1 2 , l = r − 1 g[i][j]=\begin{cases}g[l+1][r-1]+1, l<r-1\\2,l=r-1\end{cases} g[i][j]={g[l+1][r−1]+1,l<r−12,l=r−1最后将四种情况加起来即可， f [ i ] [ j ] = ∑ g [ i ] [ j ] f[i][j]=\sum g[i][j] f[i][j]=∑g[i][j]返回 f [ 0 ] [ n − 1 ] − 1 f[0][n-1]-1 f[0][n−1]−1，要去掉空序列。这是个区间动态规划，外层循环枚举区间长度，内层循环枚举端点，所以我们要设法维护定长滑动窗口里的某个字母出现的最左和最右边的位置，这可以用队列来做，以 O ( 1 ) O(1) O(1)时间得到最左和最右某个字母的出现位置。代码如下：
import java.util.Arrays;
public class Solution {
// 实现一下双端队列
class Deque {
private int head, tail;
private int[] q;
public Deque(int size) {
q = new int[size];
}
public int front() {
return q[head];
}
public int back() {
return q[tail - 1];
}
public void push(int x) {
q[tail++] = x;
}
public void pop() {
head++;
}
public boolean empty() {
return tail == head;
}
public void clear() {
head = tail = 0;
}
}
public int countPalindromicSubsequences(String s) {
int MOD = (int) (1e9 + 7);
int n = s.length();
int[][] f = new int[n][n];
// 首先考虑空序列
for (int[] row : f) {
Arrays.fill(row, 1);
}
// 接着考虑区间长度为1的情形，此时多出一个回文子序列，即一个字符
for (int i = 0; i < n; i++) {
f[i][i]++;
}
Deque[] q = new Deque[4];
for (int i = 0; i < 4; i++) {
q[i] = new Deque(n);
}
// 从长度为2的区间开始考虑起
for (int len = 2; len <= n; len++) {
for (int i = 0; i < 4; i++) {
q[i].clear();
}
for (int i = 0; i < n; i++) {
q[s.charAt(i) - 'a'].push(i);
// 算左端点
int j = i - len + 1;
// 左端点没出界就继续算法逻辑
if (j >= 0) {
// 枚举四个字母，分别计算以它们开头结尾的子序列个数
for (int k = 0; k < 4; k++) {
if (!q[k].empty() && q[k].front() < j) {
q[k].pop();
}
// 队列不空的时候说明存在以'a' + k开头结尾的子序列
if (!q[k].empty()) {
// 先考虑单个字母的情形
f[j][i]++;
int l = q[k].front(), r = q[k].back();
// 可以把l < r - 1和l = r - 1两种情况写在一起，
// 因为f[l + 1][l]其实被初始化成1了
if (l < r) {
f[j][i] = (f[j][i] + f[l + 1][r - 1]) % MOD;
}
}
}
}
}
}
return (f[0][n - 1] - 1) % MOD;
}
}
时空复杂度 O ( n 2 ) O(n^2) O(n2)。
我们提供另一种方法。设 f [ i ] [ j ] f[i][j] f[i][j]是 s [ i : j ] s[i:j] s[i:j]内的非空回文子序列数量。则 f [ i ] [ i ] = 1 , i > j ⇒ f [ i ] [ j ] = 0 f[i][i]=1,i>j\Rightarrow f[i][j]=0 f[i][i]=1,i>j⇒f[i][j]=0。接下来考虑如何递推出 f [ i ] [ j ] , i < j f[i][j],i<j f[i][j],i<j。如果 s [ i ] ≠ s [ j ] s[i]\ne s[j] s[i]=s[j]，那么 s [ i ] s[i] s[i]和 s [ j ] s[j] s[j]不能同时作为回文子序列的头尾，但是仍然有可能其中一个是头尾，那么 f [ i + 1 ] [ j ] + f [ i ] [ j − 1 ] f[i+1][j]+f[i][j-1] f[i+1][j]+f[i][j−1]实际上就是以 s [ i ] s[i] s[i]头尾的非空回文子序列个数，加上以 s [ j ] s[j] s[j]头尾，再加上既不以 s [ i ] s[i] s[i]头尾也不以 s [ j ] s[j] s[j]头尾的非空子序列个数的两倍（因为重复计算了），所以此时 f [ i ] [ j ] = f [ i + 1 ] [ j ] + f [ i ] [ j − 1 ] − f [ i + 1 ] [ j − 1 ] f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1] f[i][j]=f[i+1][j]+f[i][j−1]−f[i+1][j−1]。如果 s [ i ] = s [ j ] s[i]=s[j] s[i]=s[j]，那么先考虑 s [ i + 1 : j − 1 ] s[i+1:j-1] s[i+1:j−1]内的非空回文子序列，它们左右两边拼上 s [ i ] s[i] s[i]和 s [ j ] s[j] s[j]仍然是非空回文子序列，所以总共有两种，即 s [ i + 1 : j − 1 ] s[i+1:j-1] s[i+1:j−1]内的非空回文子序列，以及 s [ i + 1 : j − 1 ] s[i+1:j-1] s[i+1:j−1]内的非空回文子序列左右两边拼上 s [ i ] s[i] s[i]和 s [ j ] s[j] s[j]。但是这两种可能含有重复或者遗漏，重复的原因在于，有可能 s [ i + 1 : j − 1 ] s[i+1:j-1] s[i+1:j−1]里面也含 s [ i ] s[i] s[i]，从而导致相同的子序列用的 s [ i ] s[i] s[i]可能是两边的，也可能是中间的某个。那么以 s [ i ] s[i] s[i]和 s [ j ] s[j] s[j]头尾的非空回文子序列被重复计算了多少次呢？首先，如果 s [ i + 1 : j − 1 ] s[i+1:j-1] s[i+1:j−1]里没有 s [ i ] s[i] s[i]出现，那么 f [ i ] [ j ] = 2 f [ i + 1 ] [ j − 1 ] + 2 f[i][j]=2f[i+1][j-1]+2 f[i][j]=2f[i+1][j−1]+2（注意这里还需要加上单个 s [ i ] s[i] s[i]，以及两个 s [ i ] s[i] s[i]拼接，这两个回文子序列），因为左右两边拼接 s [ i ] s[i] s[i]和 s [ j ] s[j] s[j]会得到不同的子序列，是没有重复计算的，否则可能会有重复计算。我们去寻找 l l l和 r r r，其中 l l l是 s [ i + 1 : ] s[i+1:] s[i+1:]里最左边的 s [ i ] s[i] s[i]字符下标， r r r是 s [ : r − 1 ] s[:r-1] s[:r−1]里最右边的 s [ i ] s[i] s[i]字符下标，如果 l = r l=r l=r，意味着 s [ i + 1 ] [ j − 1 ] s[i+1][j-1] s[i+1][j−1]里只有一个 s [ i ] s[i] s[i]出现，这时也没有重复计算，但是会遗漏两个 s [ i ] s[i] s[i]拼接，所以 f [ i ] [ j ] = 2 f [ i + 1 ] [ j − 1 ] + 1 f[i][j]=2f[i+1][j-1]+1 f[i][j]=2f[i+1][j−1]+1；如果 l < r l<r l<r，那么 s [ l + 1 : r − 1 ] s[l+1:r-1] s[l+1:r−1]内的子序列拼接 s [ l ] s[l] s[l]和 s [ r ] s[r] s[r]，和拼接 s [ i ] s[i] s[i]和 s [ j ] s[j] s[j]，所得的子序列是一模一样的，产生了重复计算，所以要将其减去，所以有 f [ i ] [ j ] = 2 f [ i + 1 ] [ j − 1 ] − f [ l + 1 ] [ r − 1 ] f[i][j]=2f[i+1][j-1]-f[l+1][r-1] f[i][j]=2f[i+1][j−1]−f[l+1][r−1]（这里并没有产生遗漏）。代码如下：
public class Solution {
public int countPalindromicSubsequences(String s) {
int n = s.length(), MOD = (int) (1e9 + 7);
int[][] f = new int[n][n];
for (int i = 0; i < n; i++) {
f[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s.charAt(i) != s.charAt(j)) {
f[i][j] = f[i][j - 1] + f[i + 1][j] - f[i + 1][j - 1];
} else {
f[i][j] = f[i + 1][j - 1] << 1;
int l = i + 1, r = j - 1;
while (l <= r && s.charAt(l) != s.charAt(j)) {
l++;
}
while (l <= r && s.charAt(r) != s.charAt(j)) {
r--;
}
if (l > r) {
f[i][j] += 2;
} else if (l == r) {
f[i][j]++;
} else {
f[i][j] -= f[l + 1][r - 1];
}
}
f[i][j] = f[i][j] < 0 ? f[i][j] + MOD : f[i][j] % MOD;
}
}
return f[0][n - 1];
}
}
时间复杂度 O ( n 3 ) O(n^3) O(n3)，空间 O ( n 2 ) O(n^2) O(n2)。
![【趋高机器视觉】机器视觉技术原理解析及解决方案[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)