合法的括号序列

[编程题]合法的括号序列

热度指数：659 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个仅包含'('、')'和'?'三种字符构成的字符串，'?'字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列？

提示：建议python考生使用pypy提交代码！

输入描述:

一个仅包含'('、')'和'?'的字符串，长度不超过2000。

输出描述:

合法序列的数量。由于数量可能过大，请对取模。

示例1

输入

????(?

输出

说明

共有2种不同的合法括号序列，"()()()"或"(())()"。

备注:

算法知识视频讲解

Mag1c0nch

发表于 2024-11-28 22:01:58

我们假设 dp[i][j] 代表在当前位 i 之前，还有 j 个左括号的情况的数量，那么很明显，初始情况下 dp[0][0]=1 如果第 i 位是可以是一个左括号，那么代表对于所有的 dp[i-1][x] ，都可以让 dp[i][x+1] 增加其权值也就是 dp[i-1][x]，因为这个左括号会拼接展开全文

莱维_

发表于 2023-03-21 13:33:36

动态规划假设字符串长度为 n，可以考虑使用动态规划求解。动态规划数组含义：令 dp[i][j] 表示前 i 个字符中，左括号比右括号多 j 个的方案数。动态规划转移方程：如果是左括号，则 dp[i+1][j+1] = dp[i][j]。如果是右括号，则 dp[i+1][j-1] 展开全文

问苍茫

发表于 2024-11-29 14:22:51

首先看数据量2000，可以开二维的2000，考虑动态规划.dp[i][j]表示前i个字符中，没有配对的左括号数量。动态转移方程：如果第i个字符为左括号'('：那么只能从前一个i-1状态的j个没有配对的左括号转移过来(多了一个没有配对的左括号)，dp[i][j+1]=dp[i-1][j];如果第i个字展开全文

阿里嘎多懒羊羊桑_

发表于 2024-11-29 16:59:36

题意给定一个仅包含'('、')'和'?'三种字符构成的字符串，'?'字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列？思路看基本上都写的dp，来个记忆化搜索的代码吧每个?字符都有两种可能，填左括号或是填右括号，可以枚举填哪个进行记忆化搜索如何判断是合法的括号序列？只需要展开全文

whiteg

发表于 2024-11-30 18:14:31

mod = 10**9 + 7 ''' dp[i][j]表示前i个字符中钦定j个左括号的序列数量 ''' s = input() n = len(s) dp = [[0]*(n + 1) for _ in range(n + 1)] dp[0][0] = 1 for i in range(1,n+1 展开全文

君鸿

发表于 2024-12-24 17:24:12

题目求的是合法的括号序列数量，那么必然左括号和右括号数量相等，都是字符串长度的二分之一，设为n。这里首先排除字符串长度是奇数的情况，直接输出0。我们使用动态规划，令dp[i]表示左括号比右括号多i个的数量，那么i的取值范围可以是0-n。初始化状态，左右括号都为0个，只有这一种情况，dp[0] = 1 展开全文