Đề bài
Các số Catalan 1, 1, 2, 5, 14, 42, … xuất hiện trong rất nhiều bài toán đếm: số chuỗi gồm n cặp ngoặc cân bằng, số cây nhị phân có n nút, số cách chia một đa giác lồi thành các tam giác. Dãy bắt đầu với C(0) = 1 và thỏa mãn C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).
Hãy viết catalan_numbers(n).
Đầu vào
n: Chỉ số của số Catalan cuối cùng cần lấy.
Đầu ra
Trả về danh sách [C(0), C(1), …, C(n)], gồm n + 1 giá trị. C(35) là số lớn nhất còn vừa trong số nguyên có dấu 64 bit, nên hãy cẩn thận tràn số ở các bước trung gian.
Ràng buộc
0 ≤ n ≤ 35
Ví dụ
Đầu vào:
n = 4
Kết quả mong đợi:
expected = [1, 1, 2, 5, 14]
Đầu vào:
long long n = 4;
Kết quả mong đợi:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Đầu vào:
long n = 4;
Kết quả mong đợi:
long[] expected = new long[] {1, 1, 2, 5, 14};
Giải thích
C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, nên danh sách là [1, 1, 2, 5, 14].
Đầu vào:
n = 0
Kết quả mong đợi:
expected = [1]
Đầu vào:
long long n = 0;
Kết quả mong đợi:
std::vector<long long> expected = {1};
Đầu vào:
long n = 0;
Kết quả mong đợi:
long[] expected = new long[] {1};
Giải thích
Chỉ cần C(0) = 1: [1].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Lưu các giá trị vào một danh sách khi tính.
Gợi ý 2
C(k + 1) là tổng theo i của C(i) × C(k − i).
Gợi ý 3
Mỗi tích trong tổng đó không vượt quá giá trị cuối cùng, nên cách tính tổng này không bao giờ tràn số trong phạm vi đề bài.
Độ phức tạp mong đợi
thời gian O(n^2), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.