Subtask 2: Quy hoạch động

Gọi \(dp[i][j]\) là số dãy độ dài i và số tận cùng là \(j\). Chúng ta cần tìm \(dp[n][n]\). Công thức như sau:

với \(i \leq j\) vì \(a[i] \geq i\)

Công thức này có thể được cài đặt trong \(O(n^3)\) vì chúng ta có \(O(n^2)\) trạng thái và mỗi bước chuyển trạng thái cần \(O(n)\)

Subtask 3: Cải tiến quy hoạch động

Cách 1: Để ý rằng \(dp[i][j]\) được tính dựa trên một dãy tổng liên tiếp các số của \(dp[i - 1]\) nên chúng ta có thể dùng prefix sum.

Đặt \(prefixSum[i][j] = dp[i][i] + ... + dp[i][j]\), khi đó

Các công thức đều có thể tính trong \(O(1)\) nên độ phức tạp là \(O(n^2)\)

Cách 2: Có thể biến đổi công thức quy hoạch động như sau:

với \(i \leq j - 1\).

Subtask 4:

Cách 1 (tổ hợp): Đáp số là số dãy ngoặc đúng có độ dài \(2n\), hay chính là số Catalan. Để chứng minh, chúng ta có thể dùng ý tưởng của bài Encode. Trong bài Encode, dãy số \(P\) tương ứng với duy nhất một dãy ngoặc đúng và ngược lại mỗi dãy ngoặc đúng cũng tương ứng với một dãy \(P\) (song ánh), nếu \(P\) thỏa mãn các điều kiện sau:

• \(P[i] \geq i\) vì phía trước dấu ngoặc đóng thứ \(i\) phải có ít nhất \(i\) ngoặc mở.
• \(P[n] = n\) vì có đúng \(n\) ngoặc mở.
• \(P\) không giảm theo định nghĩa của \(P\).

Để chứng minh tính chất song ánh, có thể dựng một dãy ngoặc đúng từ một dãy \(P\) bất kỳ thoả mãn các điều kiện trên (ánh xạ), đồng thời với mỗi dãy \(P\) ở trên có thể dựng dược một dãy ngoặc đúng (ánh xạ ngược).

Cách 2 (OEIS): Sau khi viết được công thức \(dp\), chúng ta có thể in ra vài đáp số cho \(n\) nhỏ: \(1, 1, 2, 5, 14, 42, ...\) rồi nhập vào OEIS cầu may :v