Đề bài: Một người muốn leo lên đỉnh của một cầu thang có n bậc. Mỗi lần, người đó có thể bước 1 bậc hoặc 2 bậc. Hãy viết chương trình với cách tiếp cận quy hoạch động để tính số cách khác nhau mà người đó có thể leo lên đến đỉnh cầu thang.

Input:

Dòng đầu tiên là số nguyên dương n – số bậc của cầu thang.

Output:

Một số nguyên – là số cách khác nhau để leo đến đỉnh bậc thứ n.

Ví dụ:

Giải thích:

Với n = 5, người đó có thể leo lên theo 8 cách khác nhau, ví dụ:

• 1 + 1 + 1 + 1 + 1

• 1 + 2 + 1 + 1

• 2 + 1 + 1 + 1

• 1 + 1 + 2 + 1

• 1 + 1 + 1 + 2

• 2 + 2 + 1

• 1 + 2 + 2

• 2 + 1 + 2

Tổng cộng có 8 cách leo lên bậc thứ 5.