题解 | #合法的括号序列#

合法的括号序列

http://www.nowcoder.com/questionTerminal/cd3c583ac7054a18b164fbd4ec3247c4

动态规划

假设字符串长度为 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))
全部评论

相关推荐

object3:开始给部分🌸孝子上人生第一课了
点赞 评论 收藏
分享
Allen好Iverson:我看牛客都是20-30k的 这个3.9k爆出来有点,哈哈哈哈
点赞 评论 收藏
分享
评论
2
收藏
分享
牛客网
牛客企业服务