题意1：问你一个串有几个不连续子序列（相同字母不同位置视为两个）
题意2：问你一个串有几种不连续子序列（相同字母不同位置视为一个，空串视为一个子序列）
思路1：由容斥可知当两个边界字母相同时 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + dp[i + 1][j - 1] + 1;当两个字母不同时 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]。然后区间DP即可
思路2：由思路1我们能大致知道怎么做，显然两边界字母不一样时情况是一样的。当两边字母一样时，那么就要判断中间的重复情况。
我们设l和r，表示i + 1 ~ j - 1里最左边的s[i]字母和最右边的s[i]字母
当 l == r 那么就只有一个相同字母，dp[i][j] = dp[i + 1][j - 1] + dp[i + 1][j - 1] + 1，答案为中间部分 + 中间加上两边界 + s[i]s[j]串
当 l > r，没有这个字母，dp[i][j] = dp[i + 1][j - 1] + dp[i + 1][j - 1] + 2，答案为中间部分 + 中间加上两边界 + s[i]s[j]串 + s[i]
当l < r，说明至少有两个字母，dp[i][j] = dp[i + 1][j - 1] + dp[i + 1][j - 1] - dp[l + 1][r - 1]，答案为中间部分 + 中间加上两边界 - （l，r）区间内种数，因为这里面的和s[l]，s[r]组成的串和s[i]，s[j]重复
代码1：
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = 1e3 + ;
const ll MOD = 1e4 + ;
const int INF = 0x3f3f3f3f;
int dp[maxn][maxn]; //i到j种数
char s[maxn];
int main(){
int t, ca = ;
scanf("%d", &t);
while(t--){
scanf("%s", s + );
int n = strlen(s + );
for(int i = ; i <= n; i++){
dp[i][i] = ;
}
for(int len = ; len <= n; len++){
for(int i = ; i + len - <= n; i++){
int j = i + len - ;
if(s[i] == s[j]){
dp[i][j] = dp[i + ][j] + dp[i][j - ] + ;
}
else{
dp[i][j] = dp[i + ][j] + dp[i][j - ] - dp[i + ][j - ];
}
dp[i][j] = (dp[i][j] + MOD) % MOD;
}
}
printf("Case %d: %d\n", ca++, dp[][n]);
}
return ;
}
代码2：
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = 1e3 + ;
const ll MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
ll dp[maxn][maxn]; //i到j种数
char s[maxn];
int main(){
int t, ca = , n;
scanf("%d", &t);
while(t--){
scanf("%s", s + );
int n = strlen(s + );
for(int i = ; i <= n; i++){
dp[i][i] = ;
}
for(int len = ; len <= n; len++){
for(int i = ; i + len - <= n; i++){
int j = i + len - ;
if(s[i] == s[j]){
int l = i + , r = j - ;
while(s[l] != s[i] && l <= r) l++;
while(s[r] != s[i] && l <= r) r--;
if(l > r){
dp[i][j] = dp[i + ][j - ] + dp[i + ][j - ] + ;
}
else if(l == r){
dp[i][j] = dp[i + ][j - ] + dp[i + ][j - ] + ;
}
else{
dp[i][j] = dp[i + ][j - ] + dp[i + ][j - ] - dp[l + ][r - ];
}
}
else{
dp[i][j] = dp[i + ][j] + dp[i][j - ] - dp[i + ][j - ];
}
}
}
printf("Case %d: %lld\n", ca++, dp[][n]);
}
return ;
}