011Climbing Stairs

Problem

你正在爬一段有 n 阶的楼梯。

每次你可以爬 1 阶或 2 阶。

请你计算，有多少种不同的方法可以爬到楼顶。

Examples

示例 1

Input:  n = 2
Output: 2

解释：有两种方法可以爬到楼顶：

• 1 + 1
• 2

示例 2

Input:  n = 3
Output: 3

解释：有三种方法可以爬到楼顶：

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

示例 3

Input:  n = 4
Output: 5

解释：有五种方法可以爬到楼顶：

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

Constraints

• $1 \leq$ n $\leq 45$