Solutions of Regular bracket sequence

Select solution language

ghunglt Created at 6 likes

Ta cần đếm số cách thay thế các ký tự `?` trong chuỗi thành `(` hoặc `)` để thu được một dãy ngoặc đúng. Khởi tạo mảng `dp[i][j]` với `i` là vị trí trong sâu, `j` là số ngoặc mở hiện tại. Ban đầu `dp[0][0]=1`.Ta xét kí tự thứ `i`: - Trường hợp 1: `s[i]=='?'` hoặc `s[i]=='('` và `j>0` thì `f[i][j] = (f[i][j] + f[i-1][j-1]) % mod`. - Trường hợp 2: `s[i] == '?'` hoặc `s[i] == ')'` và `j+1<N` thì `f[i][j] = (f[i][j] + f[i-1][j+1]) % mod`. Code: https://ray.so/KRABlkK

minhpnk2 Created at 2 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)