动态规划

假设字符串长度为 n，可以考虑使用动态规划求解。

动态规划数组含义：

令 dp[i][j] 表示前 i 个字符中，左括号比右括号多 j 个的方案数。

动态规划转移方程：

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))