题目内容

你站在一栋楼的最底层，面前有一段通往楼顶的楼梯。整段楼梯共有 $n$ 级台阶。从当前位置开始，你每次只能向上走 $1$ 级台阶，或者一次向上走 $2$ 级台阶。每一步选择不同，最终到达楼顶时经过的台阶序列也会不同。

请你计算：在“每次只能走 $1$ 级或 $2$ 级”的前提下，从起点走到楼顶共有多少种不同的走法。

约束条件：楼梯的台阶数 $n$ 满足 $1 \le n \le 45$。

输入描述

输入包含一个参数：一个整数 n，表示楼梯的总台阶数。

输出描述

返回一个整数，表示从起点到达楼顶的不同走法数量。

样例1

输入

1

输出

1

说明

只有 1 种走法：直接向上走 1 级台阶。因此输出为 1。

样例2

输入

4

输出

5

说明

到达第 4 级台阶的走法可以按最后一步分类：

如果最后一步走 1 级，则此前需要到达第 3 级，有 3 种方法； 如果最后一步走 2 级，则此前需要到达第 2 级，有 2 种方法。

因此总数为 $3 + 2 = 5$。这些走法分别为 $1+1+1+1$、$1+1+2$、$1+2+1$、$2+1+1$、$2+2$。

样例3

输入

45

输出

1836311903

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写