蓝桥杯Java括号序列

本算法需要把问题分解成三步：

第一步：算出 ((() 填充 ( 的方案

第二步：算出 ((() 填充 ) 的方案

第三步：把两个方案相乘

第二步可以把原方案当成将 ((() 逆转成 ())) 再填充 ( ，这样就可以重复第一步用的算法

第一步中做动态规划

f[i][j]表示第i个右括号左边填充j个左括号的可用的方案数

f[i][j] = f[i-1][0~j]的方案和

cnt1表示需要的总左括号数

f[1][1~cnt1]方案都只有一个

f[1][0]如果不成立方案数为0否则为1

注意：

这个算法可以利用优化简化复杂度，具体相见代码f[i][j]对j有要求，j最小是当前右括号个数减去当前位置的左边的括号数（这个在遍历数组的时候利用前缀和求解），也就是所需的左括号的最小（如果为负最小值为0）。注意要取余数，最后相乘之后也需要求余 import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 // 先算一次只加左括号的方案 // 再算只加右括号的方案（镜像对称即可） // 两方案相乘 public class Main{ static long M = 1000000007; static char[] cs; public static void main(String[] args){ Scanner sc = new Scanner(System.in); cs = sc.nextLine().toCharArray(); long ans = clac(); int n = cs.length; for(int i = 0,j = n-1;i < j;i++,j--){ char temp = cs[i]; cs[i] = cs[j]; cs[j] = temp; } for(int i = 0;i < n;i++){ if(cs[i] == '(')cs[i] = ')'; else cs[i] = '('; } ans *= clac();// 反转后再来一遍 System.out.println(ans%M); } public static long clac(){ int[] sum = new int[5001]; int cnt1 = 0; int cnt2 = 0; int n = 0; long[][] f = new long[5001][5001];// 遍历第i个，添加j个左括号的结果 int ri = 1; for(char c:cs){ if(c == '('){ sum[ri]++; cnt2++; }else{ ri++; n++; if(cnt2 == 0){ cnt1++; }else{ cnt2--; } } } for(int i = 1;i <= n;i++){// SUM转为前缀和 sum[i] += sum[i-1]; } for(int j = 0;j <= cnt1;j++){ f[1][j] = 1; } if(sum[1] == 0){// 如果第一个右括号前没有左括号，不加括号的方案无效 f[1][0] = 0; } // for(int i = 2;i <= n; i++){// 遍历右括号 // for(int j = Math.max(0,i-sum[i]);j <= cnt1;j++){// 加多少左括号，注意有下限 // for(int k = 0;k <= j;k++){ // f[i][j] = (f[i][j] + f[i-1][k])%M; // } // } // } // 优化上文的算法 for(int i = 2;i <= n; i++){// 遍历右括号 long[] ne = new long[cnt1+1]; ne[0] = f[i-1][0]; for(int k = 1;k <= cnt1;k++){ ne[k] = ne[k-1] + f[i-1][k]; ne[k] %= M; } for(int j = Math.max(0,i-sum[i]);j <= cnt1;j++){// 加多少左括号，注意有下限 f[i][j] += ne[j]; } } return f[n][cnt1]; } }