该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你正在爬一个楼梯，楼梯总共有 $n$ 阶台阶。 每次你可以选择爬 $1$ 阶 或者 $2$ 阶。

问：从第 $0$ 阶到达第 $n$ 阶有多少种不同的走法？

输入格式

输入一个整数 $n$ （$1≤n≤45$）。

输出格式

输出一个整数，表示不同的走法数量。

样例

2

2

3

3

样例解释

对于第一个样例：

有两种方法可以爬到楼顶。

• 1 阶 + 1 阶

• 2 阶

对于第二个样例：

有三种方法可以爬到楼顶。

• 1 阶 + 1 阶 + 1 阶

• 1 阶 + 2 阶

• 2 阶 + 1 阶