题目描述

有一段楼梯共有 $n$ 阶。每次可以向上走 1 阶或 2 阶。请计算从地面走到第 $n$ 阶一共有多少种不同走法。

输入格式

一行输入一个正整数 $n$。

输出格式

输出一个整数，表示走到第 $n$ 阶的方案数。

输入输出样例

输入

5

输出

8

数据范围与提示

对于全部数据，$1 \le n \le 40$。

可以令 $dp[i]$ 表示走到第 $i$ 阶的方法数。初值为 $dp[1]=1$、$dp[2]=2$，转移为 $dp[i]=dp[i-1]+dp[i-2]$。

来源

GESP 6 级动态规划训练。