Bracket sequence

Given string?s?made up with?(,?),??, count the way to substitude???with?(?or?)?to form regular bracket sequence.

Input

A string?s.

(1≤|s|≤1000)

Ouptut

An integer denotes the number of ways modulo?(109+7).

Sample input

????

Sample output

2

思路：dp[x][y]字符串長為x時(shí)，左括號(hào)還有y個(gè)未匹配。

#include<iostream> #include<cstring> using namespace std; const int mm=1009; const int mod=1e9+7; char s[mm]; int dp[2][mm]; int main() {while(cin>>s){int len=strlen(s);memset(dp,0,sizeof(dp));dp[0][0]=1;int z=0;for(int i=1;i<=len;i++){if(s[i-1]=='('){for(int j=1;j<=i;j++)dp[z^1][j]=dp[z][j-1];dp[z^1][0]=0;}else if(s[i-1]==')'){for(int j=0;j<i;j++)dp[z^1][j]=dp[z][j+1];}else{for(int j=1;j<=i;j++)dp[z^1][j]=dp[z][j-1];dp[z^1][0]=0;for(int j=0;j<i;j++)dp[z^1][j]=(dp[z][j+1]+dp[z^1][j])%mod;}z^=1;}cout<<dp[z][0]<<"\n";} }

轉(zhuǎn)載于:https://www.cnblogs.com/nealgavin/archive/2013/03/13/3206130.html

總結(jié)

以上是生活随笔為你收集整理的LS 24 Bracket sequence(DP)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。