DQCB03 — NHỮNG BẬC THANG

Đề bài

Một bạn học sinh đứng ở chân cầu thang có $N$ bậc. Trong mỗi lần di chuyển, bạn có thể bước lên 1 bậc hoặc 2 bậc.

Hãy tính số cách khác nhau để đi từ chân cầu thang lên đúng bậc thứ $N$.

Hai cách được coi là khác nhau nếu trình tự các bước 1 bậc hoặc 2 bậc khác nhau.

Ví dụ: Với $N=4$, có 5 cách:

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 2 + 2

Bài này khuyến khích sử dụng đệ quy có ghi nhớ, vì đệ quy thông thường sẽ tính đi tính lại nhiều bài toán con giống nhau.

Dữ liệu vào

Một dòng chứa số nguyên dương $N$.

Dữ liệu ra

Một số nguyên duy nhất: số cách đi lên đúng bậc thứ $N$.

Giới hạn

$1 \le N \le 80$.

Kết quả nằm trong phạm vi số nguyên có dấu 64-bit (long long trong C++).

Ví dụ 1

Input

4

Output

5

Ví dụ 2

Input

5

Output

8

Gợi ý tư duy đệ quy

Gọi F(n) là số cách đi hết n bậc còn lại.

1. Nếu bước đầu tiên đi 1 bậc thì còn lại bài toán con nào?
2. Nếu bước đầu tiên đi 2 bậc thì còn lại bài toán con nào?
3. Hai trường hợp bước đầu không trùng nhau. Vậy cần cộng hay nhân số cách của hai bài toán con?
4. F(0)=1 có nghĩa gì? (Có đúng một cách: không cần bước thêm.)
5. Vì sao nên lưu kết quả F(n) sau lần tính đầu tiên?