Advertisement
kolbka_

Untitled

Dec 10th, 2021
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.58 KB | None | 0 0
  1. int main(){
  2. string x;
  3. cin >> x;
  4. int n = x.size();
  5. vector<vector<int>> dp(n+3, vector<int>(n+4));
  6. dp[0][0] = 1;
  7. for (int i = 1; i <= n; i++){
  8. for (int balance = 1; balance <= n/2; balance++){
  9. if (x[i] == '('){
  10. dp[i][balance] = dp[i-1][balance-1];
  11. }
  12. else if (x[i] == ')'){
  13. dp[i][balance] = dp[i+1][balance+1];
  14. }
  15. else{
  16. dp[i][balance] = dp[i-1][balance-1] + dp[i+1][balance+1];
  17. }
  18. }
  19. }
  20. cout << dp[n][n/2];
  21. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement