Đếm số cách leo cầu thang với bước 1 hoặc 2 bậc
Một cầu thang có n bậc. Mỗi lần bước, bạn chỉ được bước lên 1 bậc hoặc 2 bậc. Đây là
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, loops.
Nội dung đề bài
Mô tả bài toán
Một cầu thang có n bậc. Mỗi lần bước, bạn chỉ được bước lên 1 bậc hoặc 2 bậc. Đây là bài quy hoạch động đầu tiên mà gần như ai học thuật toán cũng gặp: muốn biết số cách lên tới bậc n, ta phải nhìn vào số cách lên tới hai bậc ngay dưới nó.
Yêu cầu
Cho số bậc n, hãy đếm số dãy bước khác nhau để đi từ mặt đất (bậc 0) lên đúng bậc thứ n. Hai cách được xem là khác nhau nếu dãy độ dài các bước khác nhau, ví dụ 1+1+2 khác 1+2+1.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và ghi kết quả ra stdout. Chỉ in đúng một số nguyên trên một dòng, không in thêm chữ nào khác và không in dấu cách thừa.
Input
- Một dòng duy nhất chứa số nguyên n (1 <= n <= 40).
Output
- Một số nguyên trên một dòng: số cách leo hết cầu thang. Với n <= 40 kết quả không vượt
quá 165580141.
Ràng buộc
- Chỉ được dùng bước dài 1 hoặc 2 bậc, không được bỏ qua bậc nào.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
1
Output
1
Ví dụ 2
Input
2
Output
2
Giải thích
Với n = 4 có đúng 5 cách: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2. Vậy in ra:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
