小 A 有一个只包含左右括号的字符串 S. 但他觉得这个字符串不够美观, 因为它不是一个合法的括号串. 一个合法的括号串是这样定义的:
1. ()是合法的括号串
2. 若 A 是合法的括号串, 则 (A) 则是合法的括号串
3. 若 A,B 是合法的括号串, 则 AB 也是合法的括号串.
小 A 现在希望删掉 S 中若干个字符, 使得剩下的字符串是一个合法的括号串. 小 A 想知道有多少不同的方案. 两个方案是不同的, 当且仅当他们删除的位置不同. 比如当 S 是 (() 时, 有两种方案. 分别是删掉第一个位置, 或是删掉第二个位置.
输入描述:
第一行一个整数 n, 代表 S 的长度.
第二行输入 n 个字符, 字符要么是(, 要么是). 代表串 S.
输出描述:
一行一个整数, 代表不同的方案数. 答案对 10^9+7 取模.
示例 1
输入
复制
8 )(()(())
输出
复制
30
备注:
- 20%: n <= 20
- 40%: n <= 100
- 60%: n <= 1000
- 100%: n <= 10000
动态规划, 但是只需要使用一维的 DP
dp[j]就意味着还有多少个左括号 也就是'(';
原因十分的简单, 根据题目要求我们就可以知道, 左括号需要和右括号匹配, 但是只有一个右括号是没有什么用的.
打个比方 : () 就可以成为一个合法的括号串;
)( 就不可以成为一个合法的括号串.
现在, 接着讲 DP;
这道题 DP 的转移方程, 就可以看代码了.
关于 DP 的问题, 可以在评论区中问.
- #include<bits/stdc++.h>
- using namespace std;
- #define mod 1000000007
- char ch[10001];
- long long dp[10001];
- int main()
- {
- int n;
- cin>>n;
- cin>>ch;
- dp[0]=1;
- for(int i=0;i<n;i++)
- {
- if(ch[i]=='(')
- {
- for(int j=n-i;j>=0;j--) dp[j+1]=(dp[j+1]+dp[j])%mod;
- }
- else
- {
- for(int j=1;j<=n-i;j++) dp[j-1]=(dp[j-1]+dp[j])%mod;
- }
- }
- cout<<((dp[0]-1)+mod)%mod;
- return 0;
- }
来源: https://www.cnblogs.com/FXY-180/p/9609443.html