Solutions of Regular bracket sequence

Select solution language

minhpnk2 Created at 0 likes

## Nhận xét - Một dãy ngoặc được gọi là dãy ngoặc đúng khi và chỉ khi - Số ngoặc mở bằng số ngoặc đóng - $\forall$ tiền tố chuỗi ngoặc thì số ngoặc mở phải **lớn hơn hoặc bằng** số ngoặc đóng - Vì thế ta phải *kệ* trước những dãy ngoặc mà số ngoặc đóng nhỏ hơn số ngoặc mở - Ta gọi $dp[i][j]$ là số dãy ngoặc có số ngoặc mở là $i$ và số ngoặc đóng là $j$ - **Nghiệm của bài toán:** $dp[\frac{n}{2}][\frac{n}{2}]$ (Với $n$ chẵn còn $n$ lẻ thì bằng $0$) ## Thuật toán - Ta duyệt từng kích thước của dãy ngoặc. Gọi là $sz$ - Với mỗi kích thước dãy ngoặc, ta duyệt từng số ngoặc mở. Gọi là $i$ - Với mỗi số ngoặc mở: - Ta gọi $j$ là số lượng ngoặc đóng thông qua công thức $j = sz - i$ - Nếu $i > j: dp[i][j] = 0$ - Nếu $i \le j$ - $dp[i][j] = dp[i - 1][j]$ nếu $s[i] = '('$ - $dp[i][j] = dp[i][j - 1]$ nếu $s[i] = ')'$ - $dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$ nếu $s[i] = '?'$ Code tham khảo [tại đây](https://marisaoj.com/submission/906089)