Java题解：动态规划

解题思路:

注意事项:

参考代码:package com.test.eazy;

import java.util.Scanner;

public class eazy10 {
   static final int N = 5005;
   static final int MOD = 1000000007;
   static int[][] f = new int[N][N];
   static String s;
   static int n;

   static long get() {
       // 初始化动态规划数组
       for (int i = 0; i <= n; i++) {
           for (int j = 0; j <= n; j++) {
               f[i][j] = 0;
           }
       }
       f[0][0] = 1;

       // 动态规划填表
       for (int i = 1; i <= n; i++) {

           if (s.charAt(i - 1) == '(') {
               for (int j = 1; j <= n; j++) {
                   f[i][j] = f[i - 1][j - 1];
               }
           } else { // 当前字符为 ')'
               f[i][0] = (f[i - 1][1] + f[i - 1][0]) % MOD;
               for (int j = 1; j <= n; j++) {
                   f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % MOD;
               }
           }
       }

       // 寻找最终结果
       for (int i = 0; i <= n; i++) {
           if (f[n][i] != 0) {
               return f[n][i];
           }
       }
       return -1;
   }

   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       s = scanner.next();
       n = s.length();
       long x = get();

       // 反转字符串，并将'('转换为')'，')'转换为'('
       s = new StringBuilder(s).reverse().toString();
       s = s.replace(')', 't'); // 使用临时字符't'来避免直接交换
       s = s.replace('(', ')');
       s = s.replace('t', '(');

       long y = get();

       System.out.println((x * y) % MOD);
   }
}