Dãy ngoặc đúng với n<=1000

#1

Cho mình hỏi bài toán như sau: Mình đã làm rồi nhưng chỉ chạy được gần đến 100 thôi bằng nhánh cận. Tuy nhiên dữ liệu bài toán lại cho n<=1000.
Bài toán như sau: Hãy đếm xem có bao nhiêu dãy ngoặc đúng có độ dài n (n là số chẵn). Với (n<=1000).
Điều kiện: Nếu A là dãy ngoặc đúng thì (A) cũng là dãy ngoặc đúng

  • Nếu A,B là dãy ngoặc đúng thì AB cũng là dãy ngoặc đúng.
    Ví dụ (), ()(), (()()),… là các dãy ngoặc đúng. Còn )))()()))) không là dãy ngoặc đúng!

Ví dụ:
Input n = 4.
Output 2

Giải thích: Hai dãy ngoặc đúng là ()() và (())

Mình cảm ơn!

#2

Hình như với dữ liệu n<1000 thì phải sử dụng QHĐ thì phải nhưng em ko biết phải sử dụng như thế nào do em chưa thành thạo lắm. Mong các ac giúp e thuật toán với ạ!

#3

n là số chẵn, nên n = 2m, với m là số nguyên.

Công thức số dãy ngoặc đúng cũng là số Catalan:
C(m) = (2m)! / ( m! (m+1)! )

3 Likes
#4

Cảm ơn anh! Vậy nếu như in ra các cách thì thuật toán tối ưu nhất có thể chạy được đến mức nào ạ!

#5

Phương pháp liệt kê thì có backtracking và generation.

Backtracking thì xét thêm các điều kiện để tránh các lần thử không cần thiết, thường gọi là heuristics: số lượng ) ít hơn hoặc bằng (, số lượng ( không nhiều hơn số lần thử còn lại.

Còn generation thì không biết, mình có làm rồi nhưng lâu quá không nhớ.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?