括号序列计数：动态规划求解'('，')'和'?'组成的合法序列数量

可以利用动态规划来解决这个问题。\n\n定义一个二维数组dp，其中dp[i][j]表示字符串从索引i到索引j之间可以组成的合法括号序列的数量。\n\n首先，对于长度为1的字符串，只有一个字符，它必须是'('或')'，所以dp[i][i] = 0，如果该字符是'('或')'，则dp[i][i] = 1。\n\n然后，对于长度大于等于2的字符串，我们可以考虑两种情况：\n1. 如果字符串的最后两个字符是'()'，则可以将这两个字符组成一对合法的括号，剩余部分为dp[i][j-2]；\n2. 如果字符串的最后两个字符是'?'和')'，则可以将'?'替换为'('，将这两个字符组成一对合法的括号，剩余部分为dp[i][j-2]；\n3. 如果字符串的最后两个字符是'('和'?'，则可以将'?'替换为')'，将这两个字符组成一对合法的括号，剩余部分为dp[i][j-2]；\n4. 如果字符串的最后两个字符是'?'和'?'，则可以将'?'替换为'('，将这两个字符组成一对合法的括号，剩余部分为dp[i][j-2]；\n5. 如果字符串的最后两个字符是'('和'('，则无法组成合法的括号序列。\n\n综上所述，我们可以得到状态转移方程：\ndp[i][j] = dp[i][j-2] + dp[i+1][j-1] + dp[i+2][j-2] + ... + dp[j-2][j]，其中i+1<=j-2。\n\n最后，可以从长度为2的子串开始计算，逐步增加子串的长度，直到计算出整个字符串的结果dp[0][n-1]，其中n为字符串的长度。\n\n以下为Python代码实现：\n\ndef countValidParentheses(s):\n n = len(s)\n dp = [[0] * n for _ in range(n)]\n\n # 初始化长度为1的字符串\n for i in range(n):\n if s[i] == '(' or s[i] == ')':\n dp[i][i] = 1\n\n # 计算长度大于等于2的字符串\n for length in range(2, n + 1):\n for i in range(n - length + 1):\n j = i + length - 1\n if s[j] == ')':\n dp[i][j] = dp[i][j - 2]\n elif s[j] == '?' and s[j - 1] == ')':\n dp[i][j] = dp[i][j - 2]\n elif s[j] == '?' and s[j - 1] == '(':\n dp[i][j] = dp[i][j - 2]\n elif s[j] == '?' and s[j - 1] == '?':\n dp[i][j] = dp[i][j - 2]\n else:\n dp[i][j] = 0\n for k in range(i + 1, j - 1):\n if s[k] == '?' or s[k] == '(':\n dp[i][j] += dp[i][k - 1] * dp[k + 1][j - 1]\n\n return dp[0][n - 1]\n\n示例输入1：\ns = "((?)?)"\n输出1：\n9\n\n示例输入2：\ns = "??"\n输出2：\n2\n\n示例输入3：\ns = "(?)"\n输出3：\n1