---
# System prepended metadata

title: 'B:Parenthese'

---

---
---
# 🌱 Lời giải Mely Educational Contest 04 bài B :Parenthese.

>[color=pink] Nếu bạn cảm thấy Edit này chất lượng tiếc gì một upvote và giới thiệu team với mọi người nhé :heart: 

###### 📋 Content: 
[TOC]
____
## Nhận xét :label:
Đây là một bài nhập môn quy hoạch động, ngoài quy hoạch động bạn có thể tham khảo cách giải bài này bằng tìm dãy số catalan tại [đây](https://www.facebook.com/groups/devoiminhdidauthe/permalink/24316501041326938/).
:question: Vậy việc dùng quy hoạch động như thế nào ?
Nhận xét, ta nhận thấy dãy ngoặc độ dài $2 * N$ được dựa trên kết quả ghép lại của các dãy ngoặc có độ dài $2 * X$ và $2 * Y$ ghép lại với nhau.
:bulb: Ta suy ra được công thức như sau :
  >[color=green] 
  >- Gọi $dp_i$ là số cách tạo được dãy ngoặc đúng độ dài $2 * i$
  >- Giả sử đặt  dấu ngoặc mở tại vị trí $j + 1$ và dấu ngoặc đóng tại vị trí $2 * i$. Vậy ta sẽ tách dãy ngoặc độ dài $i$ thành hai dãy ngoặc $1$ là độ dài $2 * j$ tính từ vị trí $1$ đến vị trí $2 * j$ và một dãy ngoặc còn lại là độ dài $2 * (i - j - 1)$ tính từ vị trí $2 * j + 2$ đến vị trí $2 * i - 1$.
  >- Số lượng dãy ngoặc được tạo ra như vậy đúng bằng tích số cách tạo dãy ngoặc đúng có độ dài $2 * j$ và $2 *(i - j - 1)$
  >- Số cách tạo dãy ngoặc đúng có độ dài $2 * j$ và $2 *(i - j - 1)$ đã được tính trước đó nên ta có thể áp dụng để tích dãy ngoặc đúng có độ dài $2*i$.

## Code mẫu :bulb: 
> **Time:** $O(n^{2})$
> **Space:** $O(n)$ 
> **Algo:** Dynamic programing.
> [color=lightgreen] 
:::success
:::spoiler code của LeThanhMinh
 ``` cpp
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const ll MAXN = 1e6 + 7;
const ll MOD = 1e9 + 7;
ll val = 0 , n;
ll dp[MAXN];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    dp[0] = 1; 
    for(int i = 1 ; i <= n ; i ++){
      for(int j = 0 ; j <= i - 1 ; j ++){
        dp[i] += (dp[i - j - 1] * dp[j]) % MOD;
        dp[i] %= MOD;
      }
    }
    cout << dp[n] % MOD;
    return 0;
    
}
```
:::success

