核心思想
区间dp：大范围的问题拆分成若干小范围的问题来求解 可能性展开的常见方式：
1）基于两侧端点讨论的可能性展开
2）基于范围上划分点的可能性展开
例题
1、完成配对需要的最少字符数量
题目描述： 给定一个由 '[' ，']'，'('，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。
例如当前串是 "([[])"，那么插入一个']'即可满足。 数据范围：字符串长度满足 1≤n≤100 1≤n≤100
输入描述：
仅一行，输入一个字符串，字符串仅由 '[' ，']' ，'(' ，‘)’ 组成 输出描述：
输出最少插入多少个括号 示例1 输入： ([[]) 输出： 1 示例2 输入： ([])[] 输出： 0
解题思路：
dp[i][j]: 表示在s[i, j]的范围内区号区间匹配需要插入的括号数有多少这里主要有2个分类讨论
s[i, j]是一组，即类似【(([ ]))】这类
s[i, j]其实包含多组符号，即【】（【】）() 这种，即基于每个可能的划分点，做左右划分，那么就可以分为2个部分
代码如下：
package main.java.class077;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_MinimumInsertionsToMatch
* @description: 完成配对需要的最少字符数量
* // 给定一个由'['、']'、'('，')'组成的字符串
* // 请问最少插入多少个括号就能使这个字符串的所有括号正确配对
* // 例如当前串是 "([[])"，那么插入一个']'即可满足
* // 输出最少需要插入多少个字符
* // 测试链接 : https://www.nowcoder.com/practice/e391767d80d942d29e6095a935a5b96b
* @author: zs宝
* @create: 2025-09-15 11:01
* @Version 1.0
**/public class Code01_MinimumInsertionsToMatch {
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
String str = buffer.readLine();
out.println(compute(str));
out.flush();
out.close();
buffer.close();
}
public static int compute(String str) {
char[] s = str.toCharArray();
int n = s.length;
int[][]dp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = -1;
}
}
return f1(s, 0, n - 1, dp);
}
//dp[i][j]:表示在s[i,j]的范围内区号区间匹配需要插入的括号数有多少
public static int f1(char[]s, int i, int j, int[][]dp) {
if (i == j) {
return 1;
}
if (i + 1 == j) {
if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')) {
return 0;
}
return 2;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
//当i,j之间有多个字符时
//这个时候有两种可能
//第一种可能：i,j是一组符号,即 [l]、[r]本来就是配对的
//第二种可能：i,j之间可以并行，即有2组符号，即基于每个可能的划分点，做左右划分
int p1=Integer.MAX_VALUE;
if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')){
p1=f1(s,i+1,j-1,dp);
}
int p2=Integer.MAX_VALUE;
for(int m=i;m<j;m++){
p2=Math.min(p2,f1(s,i,m,dp)+f1(s,m+1,j,dp));
}
int ans=Math.min(p1,p2);
dp[i][j]=ans;
return ans;
}
}
}2、涂色 & 奇怪打印机
测试链接：
https://leetcode.cn/problems/strange-printer/ 题目描述如下： 有台奇怪的打印机有以下两个特殊要求：
打印机每次只能打印由 同一个字符 组成的序列。
每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1：
输入：s = "aaabbb" 输出：2 解释：首先打印 "aaa" 然后打印 "bbb"。
示例 2：
输入：s = "aba" 输出：2 解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示：
1 <= s.length <= 100s由小写英文字母组成
解题思路：
定义
dp[l][r]为子串s[l..r]刷成目标串的最少次数。首先明确一点先从两端刷起，一定不会错过最优解
若
s[l]==s[r]，那么l,r位置可以同时刷掉，即将[l,r]一股脑刷完按照以往的思路我们接下来应该考虑的是[l+1,r-1]范围上的内容
但是这里我们考虑的是[l,r-1]的内容，r位置将在[l,r-1]最后刷的时候顺带刷掉
为什么是[l,r-1]呢？这是因为我们不知道[l+1,r-1]之间是否还有其它位置的颜色与l，r相同
有可能在第一次刷l,r的时候，内部的也被解决了，如AAAAAA这种
若不等
则基于范围上划分点的可能性展开
代码如下：
package main.java.class077;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_Coloring
* @description: 涂色 & 奇怪打印机
* // 假设你有一条长度为5的木板，初始时没有涂过任何颜色
* // 你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红
* // 用一个长度为5的字符串表示这个目标：RGBGR
* // 每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色
* // 例如第一次把木板涂成RRRRR
* // 第二次涂成RGGGR
* // 第三次涂成RGBGR，达到目标
* // 返回尽量少的涂色次数
* // 测试链接 : https://www.luogu.com.cn/problem/P4170
* // 测试链接 : https://leetcode.cn/problems/strange-printer/
* @author: zs宝
* @create: 2025-09-16 09:27
* @Version 1.0
**/public class Code02_Coloring {
public static void main(String[] args) throws IOException {
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
String str=buffer.readLine();
out.println(strangePrinter1(str));
out.flush();
out.close();
buffer.close();
}
//记忆化搜索的版本
public static int strangePrinter1(String str){
char[]s=str.toCharArray();
int n=s.length;
int[][]dp=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dp[i][j]=-1;
}
}
return f1(s,0,n-1,dp);
}
public static int f1(char[]s,int l,int r,int[][]dp){
if(l>r){
return 0;
}
if(l==r){
return 1;
}
if(l+1==r){
return s[l]==s[r]?1:2;
}
if(dp[l][r]!=-1){
return dp[l][r];
}
int ans=Integer.MAX_VALUE;
//当l,r之间有多个的时候
//先从两端刷起，一定不会错过最优解
//这是因为：两端刷完后，范围变小只用刷中间的，两段不会再改变
if(s[l]==s[r]){
//若s[l]==s[r]，那么l,r位置可以同时刷掉，即将[l,r]一股脑刷完
//按照以往的思路我们接下来应该考虑的是[l+1,r-1]范围上的内容
//但是这里我们考虑的是[l,r-1]的内容，r位置将在[l,r-1]刷的时候顺带刷掉
//为什么是[l,r-1]呢？这是因为我们不知道[l+1,r-1]之间是否还有其它位置的颜色与l，r相同
//有可能在第一次刷l,r的时候，内部的也被解决了，如AAAAAA这种
ans=Math.min(ans,f1(s,l,r-1,dp));
}else {
//若不等，则基于范围上划分点的可能性展开
for(int m=l;m<r;m++){
ans=Math.min(ans,f1(s,l,m,dp)+f1(s,m+1,r,dp));
}
}
dp[l][r]=ans;
return ans;
}
//严格依赖位置的动态规划
public static int strangePrinter2(String str){
char[]s=str.toCharArray();
int n=s.length;
int[][]dp=new int[n][n];
dp[n-1][n-1]=1;
for(int i=0;i<n-1;i++){
dp[i][i]=1;
dp[i][i+1]=s[i]==s[i+1]?1:2;
}
for(int l=n-3;l>=0;l--){
for(int r=l+2;r<n;r++){
dp[l][r]=Integer.MAX_VALUE;
if(s[l]==s[r]){
dp[l][r]=Math.min(dp[l][r],dp[l][r-1]);
}else{
for(int m=l;m<r;m++){
dp[l][r]=Math.min(dp[l][r],dp[l][m]+dp[m+1][r]);
}
}
}
}
return dp[0][n-1];
}
}3、合唱队
题目描述： 为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 n 个人，第 i 个人的身高为 hi 米（1000≤hi≤2000），并已知任何两个人的身高都不同。假定最终排出的队形是 A 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终排出的队形中：
第一个人直接插入空的当前队形中。
对从第二个人开始的每个人，如果他比前面那个人高（h 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（h 较小），那么将他插入当前队形的最左边。
当 n 个人全部插入当前队形后便获得最终排出的队形。
例如，有 6 个人站成一个初始队形，身高依次为 1850,1900,1700,1650,1800,1750， 那么小 A 会按以下步骤获得最终排出的队形：
1850。
1850,1900，因为 1900>1850。
1700,1850,1900，因为 1700<1900。
1650,1700,1850,1900，因为 1650<1700。
1650,1700,1850,1900,1800，因为 1800>1650。
1750,1650,1700,1850,1900,1800，因为 1750<1800。
因此，最终排出的队形是 1750,1650,1700,1850,1900,1800。
小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。
请求出答案对 19650827 取模的值。 输入格式： 第一行一个整数 n。 第二行 n 个整数，表示小 A 心中的理想队形。 输出格式： 输出一行一个整数，表示答案 mod19650827 的值。 输入输出样例 输入
4
1701 1702 1703 1704输出
8解题思路：
定义三维 DP：
dp[l][r][0]：从子序列arr[l..r]形成目标队形的方案数，且arr[l]是最后一个被插入的。
dp[l][r][1]：同理，arr[r]是最后一个被插入的。最终答案是
dp[1][n][0]+dp[1][n][1](mod19650827)
每个范围枚举最后插入的是左端点，还是又断点的情况
惯性思维：
这道题最开始惯性思维是思考谁最先插入的问题，但是从最先插入思考反而十分困难，各种判定模糊不清晰
代码如下：
package main.java.class077;
import java.io.*;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_HeightAndChoir
* @description: 合唱队
* // 具体描述情打开链接查看
* // 测试链接 : https://www.luogu.com.cn/problem/P3205
* @author: zs宝
* @create: 2025-09-16 10:30
* @Version 1.0
**/public class Code03_HeightAndChoir {
public static int MAXN=1001;
public static int[]arr=new int[MAXN+1];
public static int n;
public static int[][] dp = new int[MAXN][2];
public static int MOD=19650827;
public static void main(String[] args) throws IOException {
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in=new StreamTokenizer(buffer);
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken()!=StreamTokenizer.TT_EOF){
n=(int)in.nval;
for(int i=1;i<=n;i++){
in.nextToken();
arr[i]=(int)in.nval;
}
if(n==1){
out.println(1);
}else{
out.println(compute2());
}
}
out.flush();
out.close();
buffer.close();
}
public static int compute1(){
//dp[i][j]：表示arr[i,j]的方式有多少种
// dp[l][r][0] : 形成l...r的状况的方法数，同时要求l位置的数字是最后出现的
// dp[l][r][1] : 形成l...r的状况的方法数，同时要求r位置的数字是最后出现的
int[][][]dp=new int[n+1][n+1][2];
for(int i=1;i<=n-1;i++){
if(arr[i]<arr[i+1]){
dp[i][i+1][0]=1;
dp[i][i+1][1]=1;
}
}
for(int i=n-2;i>=1;i--){
for(int j=i+2;j<=n;j++){
//若最后一个插入的是左边界的点i
if(arr[i]<arr[i+1]){
dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][0])%MOD;
}
if(arr[i]<arr[j]){
dp[i][j][0]=(dp[i][j][0]+dp[i+1][j][1])%MOD;
}
//若最后插入的是右边界的点j
if(arr[j]>arr[j-1]){
dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][1])%MOD;
}
if(arr[j]>arr[i]){
dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][0])%MOD;
}
}
}
return (dp[1][n][0]+dp[1][n][1])%MOD;
}
//严格按照位置的动态规划+空间压缩
public static int compute2(){
for(int i=1;i<=n;i++){
Arrays.fill(dp[i],0);
}
if(arr[n-1]<arr[n]){
dp[n][0]=1;
dp[n][1]=1;
}
for(int i=n-2;i>=1;i--){
if(arr[i]<arr[i+1]){
dp[i+1][0]=1;
dp[i+1][1]=1;
}
for(int j=i+2;j<=n;j++){
int a=0;
int b=0;
//若最后一个插入的是左边界的点i
if(arr[i]<arr[i+1]){
a=(a+dp[j][0])%MOD;
}
if(arr[i]<arr[j]){
a=(a+dp[j][1])%MOD;
}
//若最后插入的是右边界的点j
if(arr[j]>arr[j-1]){
b=(b+dp[j-1][1])%MOD;
}
if(arr[j]>arr[i]){
b=(b+dp[j-1][0])%MOD;
}
dp[j][0]=a;
dp[j][1]=b;
}
}
return (dp[n][0]+dp[n][1])%MOD;
}
}4、移除盒子
题目描述： 给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。
返回 你能获得的最大积分和 。
示例 1：
输入：boxes = [1,3,2,2,2,3,4,3,1] 输出：23 解释： [1, 3, 2, 2, 2, 3, 4, 3, 1] ----> [1, 3, 3, 4, 3, 1] (33=9 分) ----> [1, 3, 3, 3, 1] (11=1 分) ----> [1, 1] (33=9 分) ----> [] (22=4 分)
示例 2：
输入：boxes = [1,1,1] 输出：9
示例 3：
输入：boxes = [1] 输出：1
提示：
1 <= boxes.length <= 1001 <= boxes[i] <= 100
解题思路：
这个题很难很难很难很难
但是最后的思路就只有两种
前缀先消，即能够拿到的某个数字连续前缀直接消掉，不考虑能否和后面相同的数字再连起来的情况
如2 2 2 2 3 2 2 2，当到达3时，前面的4个2已经消掉，前面的4个2不考虑先消掉中间的3和后面的2结合
前缀跟后，即前面某个数字的连续前缀保留，消除中间的部分，可以和后面的相同连续数字连接起来，然后再消
如2 2 2 2 3 2 2 2，当到达3时，由于后面由是2了，因此先将这个3消掉，让前面的2和后面的2连接起来一起消除。
如上，便是本题的转化思路，主要时跟随这个思路以往没有见到过
代码如下：
package main.java.class077;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_RemoveBoxes
* @description: 移除盒子
* // 给出一些不同颜色的盒子boxes，盒子的颜色由不同的正数表示
* // 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止
* // 每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1）
* // 这样一轮之后你将得到 k * k 个积分
* // 返回你能获得的最大积分总和
* // 测试链接 : https://leetcode.cn/problems/remove-boxes/
* @author: zs宝
* @create: 2025-09-17 09:13
* @Version 1.0
**/public class Code04_RemoveBoxes {
class Solution {
public int removeBoxes(int[] boxes) {
int n=boxes.length;
int[][][]dp=new int[n][n][n];
return f1(boxes,0,n-1,0,dp);
}
/**
l:左边界
r:右边界
k:l前面有多少数字是和l位置的数相同的,这些数字的位置必须连着的，如2 22 2 2 2这种待在一起才行
*/
public int f1(int[] boxes,int l,int r,int k,int[][][]dp){
if(l>r){
return 0;
}
if(dp[l][r][k]!=0){
return dp[l][r][k];
}
//可能性1：前缀先消
int s=l;
while(s+1<=r && boxes[s+1]==boxes[l]){
s++;
}
//最后s的位置是最后一个连续着和l位置相同的数的位置
int cnt=s+1-l+k;
//前缀先消
int ans=cnt*cnt+f1(boxes,s+1,r,0,dp);
//可能性二：前缀跟后
for(int m=s+2;m<=r;m++){
//找到后面数字和l位置数字相同的开头，只需要找到开头
//如2 222 3 22，只需要找到3后面第一个位置的2
if(boxes[m]==boxes[l] && boxes[m]!=boxes[m-1]){
// boxes[l] == boxes[m]是必须条件
// boxes[m - 1] != boxes[m]是剪枝条件，避免不必要的调用
ans=Math.max(ans,f1(boxes,s+1,m-1,0,dp)+f1(boxes,m,r,cnt,dp));
}
}
dp[l][r][k]=ans;
return ans;
}
}
}5、合并石头的最低成本
题目描述： 有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。
返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。
示例 1：
输入：stones = [3,2,4,1], K = 2 输出：20 解释： 从 [3, 2, 4, 1] 开始。 合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。 合并 [4, 1]，成本为 5，剩下 [5, 5]。 合并 [5, 5]，成本为 10，剩下 [10]。 总成本 20，这是可能的最小值。
示例 2：
输入：stones = [3,2,4,1], K = 3 输出：-1 解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.
示例 3：
输入：stones = [3,5,1,2,6], K = 3 输出：25 解释： 从 [3, 5, 1, 2, 6] 开始。 合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。 合并 [3, 8, 6]，成本为 17，剩下 [17]。 总成本 25，这是可能的最小值。
提示：
n == stones.length1 <= n <= 301 <= stones[i] <= 1002 <= k <= 30
解题思路：
这个题当，k一定，石头数量也一定时，那么整体能不能最终合成一块就定了
在最终一定能合成一块的基础上，那么中间的范围能合成多少块其实无需我们再考虑
只需要不断的枚举即可。
如何枚举：
让最前面的保证合成一块，那么后面的就一定要合成出k-1快，即一直合成到不能再合成为止
代码如下
package main.java.class077;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_MinimumCostToMergeStones
* @description: 合并石头的最低成本
* // 有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头
* // 每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数
* // 返回把所有石头合并成一堆的最低成本
* // 如果无法合并成一堆返回-1
* // 测试链接 : https://leetcode.cn/problems/minimum-cost-to-merge-stones/
* @author: zs宝
* @create: 2025-09-17 10:08
* @Version 1.0
**/public class Code05_MinimumCostToMergeStones {
class Solution {
// 时间复杂度O(n^3)
// 优化策略来自于观察
// l.....r最终会变成几份其实是注定的，根本就无法改变
// 那么也就知道，满足(n - 1) % (k - 1) == 0的情况下，
// 0....n-1最终一定是1份，也无法改变
// 如果l.....r最终一定是1份
// 那么要保证l.....m最终一定是1份，m+1...r最终一定是k-1份
// 如果l.....r最终一定是p份（p>1）
// 那么要保证l.....m最终一定是1份，那么m+1...r最终一定是p-1份
// 怎么保证的？枚举行为中，m += k-1很重要！
// m每次跳k-1！
// 如果l.....r最终一定是1份
// 就一定能保证l.....m最终一定是1份
// 也一定能保证m+1...r最终一定是k-1份
// 不要忘了，加上最后合并成1份的代价
// 如果l.....r最终一定是p份
// 就一定能保证l.....m最终一定是1份
// 也一定能保证m+1...r最终一定是p-1份
// 不用加上最后合并成1份的代价
public int mergeStones(int[] stones, int k) {
int n=stones.length;
//如果最终不能合成一份
if((n-1)%(k-1)!=0){
return -1;
}
//前缀和，在最前面增加一个0
//那么[l,r]的前缀和就为presum[r+1]-presum[l]
int[]presum=new int[n+1];
for(int i=0,j=1,sum=0;i<n;i++,j++){
sum+=stones[i];
presum[j]=sum;
}
//既然最终一定能合成一份，那么在范围内，能和多少，就让它合多少，不再考虑其他的了
// dp[l][r] : l...r范围上的石头，合并到不能再合并（份数是确定的），最小代价是多少
int[][]dp=new int[n][n];
for(int l=n-2,ans;l>=0;l--){
for(int r=l+1;r<n;r++){
ans=Integer.MAX_VALUE;
for(int m=l;m<r;m+=(k-1)){
ans=Math.min(ans,dp[l][m]+dp[m+1][r]);
}
if((r-l)%(k-1)==0){
// 最终一定能划分成一份，那么就再加合并代价
ans+=presum[r+1]-presum[l];
}
dp[l][r]=ans;
}
}
return dp[0][n-1];
}
}
}6、统计不同回文子序列
题目描述： 给你一个字符串 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 <= 1000s[i]仅包含'a','b','c'或'd'
解题思路如下图： 
代码如下：
package main.java.class077;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code06_CountDifferentPalindromicSubsequences
* @description: 统计不同回文子序列
* // 给你一个字符串s，返回s中不同的非空回文子序列个数
* // 由于答案可能很大，答案对 1000000007 取模
* // 测试链接 : https://leetcode.cn/problems/count-different-palindromic-subsequences/
* @author: zs宝
* @create: 2025-09-17 11:10
* @Version 1.0
**/public class Code06_CountDifferentPalindromicSubsequences {
class Solution {
public static int MOD = 1000000007;
public static int countPalindromicSubsequences(String str) {
char[] s = str.toCharArray();
int n = s.length;
//last存储s[i]上一次出现的位置
int[]last=new int[256];
//先分别计算出每个位置的字符最进的左右位置出现相同字符的位置
Arrays.fill(last,-1);
int[]left=new int[n];
for(int i=0;i<n;i++){
left[i]=last[s[i]];
last[s[i]]=i;
}
int []right=new int[n];
Arrays.fill(right,n);
for(int i=n-1;i>=0;i--){
right[i]=last[s[i]];
last[s[i]]=i;
}
//接下来做区间dp
long[][]dp=new long[n][n];
for(int i=0;i<n;i++){
dp[i][i]=1;
}
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
//s[i]!=s[j]时
if(s[i]!=s[j]){
dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+MOD;
}else{
//s[i]==s[j]时
int r=left[j];
int l=right[i];
if(l>r){
//当i,j中间没有s[i]这个字符时
dp[i][j]=2*dp[i+1][j-1]+2;
}else if(l==r){
//当i,j中间有一个s[i]这个字符时
dp[i][j]=2*dp[i+1][j-1]+1;
}else{
//当i,j中间有多个s[i]这个字符时
dp[i][j]=2*dp[i+1][j-1]-dp[l+1][r-1]+MOD;
}
}
dp[i][j]%=MOD;
}
}
return (int)dp[0][n-1];
}
}
}