计算括号序列数量：动态规划解法

可以使用动态规划来解决这个问题。\n\n定义状态dp[i]表示前i个字符可以组成的合法括号序列的数量。\n\n对于第i个字符，有三种情况：\n1. 如果第i个字符是'('，那么它一定可以组成一个合法括号序列，所以dp[i] = dp[i-1]。\n2. 如果第i个字符是')'，那么它只能与之前的某个'('匹配，所以需要找到最近的一个'('，将它与第i个字符组成一个合法括号序列。假设这个最近的'('在位置j，那么dp[i] = dp[j-1]。\n3. 如果第i个字符是'?'，那么它可以是'('也可以是')'，所以需要分别考虑这两种情况。如果它是'('，dp[i] = dp[i-1]；如果它是')'，需要找到最近的一个'('，将它与第i个字符组成一个合法括号序列，所以需要找到最近的一个'('，将它与第i个字符组成一个合法括号序列。假设这个最近的'('在位置j，那么dp[i] = dp[j-1]。\n\n最终的答案就是dp[n]，其中n是字符串的长度。\n\n具体的实现代码如下：\n\npython\ndef countValidParentheses(s):\n n = len(s)\n dp = [0] * (n+1)\n dp[0] = 1\n \n for i in range(1, n+1):\n if s[i-1] == '(':\n dp[i] = dp[i-1]\n elif s[i-1] == ')':\n j = i - 2\n while j >= 0:\n if s[j] == '(':\n dp[i] = dp[j]\n break\n j -= 1\n else:\n dp[i] = 2 * dp[i-1]\n j = i - 2\n while j >= 0:\n if s[j] == '(':\n dp[i] += dp[j]\n j -= 1\n \n return dp[n]\n\n\n时间复杂度：O(n^2)\n空间复杂度：O(n)