蓝桥杯 Java 括号序列

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

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

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

第三步：把两个方案相乘

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

第一步中做动态规划

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

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

cnt1表示需要的总左括号数

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

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

注意：

1. 这个算法可以利用优化简化复杂度，具体相见代码
2. f[i][j]对j有要求，j最小是当前右括号个数减去当前位置的左边的括号数（这个在遍历数组的时候利用前缀和求解），也就是所需的左括号的最小（如果为负最小值为0）。
3. 注意要取余数，最后相乘之后也需要求余

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];
  }
}