爬楼梯

假设你正在爬楼梯，需要 n 阶才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

约定

• n 是正整数。
• 第 0 阶算起点。

输入

• n：台阶数，1 <= n <= 45。

输出

方法数。

示例一

输入：

n = 2

输出：

2

解释：两种方式：1+1、2。

示例二

输入：

n = 3

输出：

3

解释：1+1+1、1+2、2+1。

复杂度要求

• 时间 O(n)，空间 O(1)。