#P14106. 【动态规划1】爬楼梯

【动态规划1】爬楼梯

题目描述

小明正在爬楼梯。楼梯总共有 n 级台阶,小明每次可以选择爬 1 级或 2 级台阶。请问小明爬到第 n 级台阶的不同方法有多少种。

注意:假设小明从地面(第 0 级台阶)开始爬楼梯,每次可以从当前台阶选择爬 1 级或 2 级台阶,直到到达第 n 级台阶。

输入

输入一个整数 n(1 ≤ n ≤ 40),表示楼梯的总级数。

输出

输出一个整数,表示爬到第 n 级台阶的不同方法数。

示例

输入 1

输出 1

输入 2

输出 2