解法

假设字符串长度为 n，可以考虑使用动态规划求解。令 dp[i][j] 表示前 i 个字符中，左括号比右括号多 j 个的方案数。考虑第 i+1 个字符：

1. 如果是左括号，则 dp[i+1][j+1] = dp[i][j]。

2. 如果是右括号，则 dp[i+1][j-1] = dp[i][j]。

3. 如果是问号，则既可以代表左括号，也可以代表右括号，因此 dp[i+1][j+1] = dp[i][j] + dp[i+1][j-1]。

最终答案即为 dp[n][0]，表示左右括号数量相等的方案数。

需要注意的是，由于原始字符串中可能存在 ? 字符，因此需要初始化 dp[0][0] = 1，并将剩余的 dp[0][j] 和 dp[i][j] 的值都设为 0。

def count_valid_parentheses(s: str) -> int:
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
        if s[i - 1] == "(":
            for j in range(i):
                dp[i][j + 1] += dp[i - 1][j]
        elif s[i - 1] == ")":
            for j in range(i):
                if j > 0:
                    dp[i][j - 1] += dp[i - 1][j]
        else:  # s[i-1] == '?'
            for j in range(i):
                dp[i][j + 1] += dp[i - 1][j]
                if j > 0:
                    dp[i][j - 1] += dp[i - 1][j]

    return dp[n][0]
s  = input()
print(count_valid_parentheses(s)%(1000000007))

import java.util.Scanner;
import java.util.*;

public class Main {
    static int mod = (int) (Math.pow(10, 9) + 7);
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] input = in.nextLine().toCharArray();
        if (input[0] == ')') {
            System.out.println(0);
            return;
        }
        int len = input.length;
        int[][] dp = new int[len][len];
        dp[0][1] = 1;
        for (int i = 0; i < len - 1; i++) {
            if (input[i + 1] == ')' || input[i + 1] == '?') {
                for (int j = 1; j < len; j++) {
                    dp[i + 1][j - 1] += dp[i][j];
                    dp[i + 1][j - 1] %= mod;
                }
            }
            if (input[i + 1] == '(' || input[i + 1] == '?') {
                for (int j = 0; j < len - 1; j++) {
                    dp[i + 1][j + 1] += dp[i][j];
                    dp[i + 1][j + 1] %= mod;
                }
            }
        }
        System.out.println(dp[len - 1][0]);
    }

}

记忆化搜索

dfs(i,j)代表前i个字符，左括号比右括号多j个的方案数

import sys
from functools import cache

sys.setrecursionlimit(10000)
def vaildNum(s: str):
    n = len(s)

    @cache
    def dfs(i: int, j: int) -> int:
        if j < 0:
            return 0
        if i == 0:
            return 1 if j == 0 else 0
        if s[i - 1] == "(":
            return dfs(i - 1, j - 1) % MOD
        elif s[i - 1] == ")":
            return dfs(i - 1, j + 1) % MOD
        else:
            return (dfs(i - 1, j - 1) + dfs(i - 1, j + 1)) % MOD

    return dfs(n, 0)


s = input().strip()
MOD = 10 ** 9 + 7
print(vaildNum(s))