Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int main(){
- string x;
- cin >> x;
- int n = x.size();
- vector<vector<int>> dp(n+3, vector<int>(n+4));
- dp[0][0] = 1;
- for (int i = 1; i <= n; i++){
- for (int balance = 1; balance <= n/2; balance++){
- if (x[i] == '('){
- dp[i][balance] = dp[i-1][balance-1];
- }
- else if (x[i] == ')'){
- dp[i][balance] = dp[i+1][balance+1];
- }
- else{
- dp[i][balance] = dp[i-1][balance-1] + dp[i+1][balance+1];
- }
- }
- }
- cout << dp[n][n/2];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement