2295. 小鹿陆陆的干饭之路
1000ms
256MB
简单
递推算法
题目描述
小鹿陆陆是一只超级爱吃苹果的梅花鹿。今天，饲养员把一盘新鲜的红苹果放在了高高的“美味平台”上。从陆陆站立的地面到美味平台，刚好有一条 $n$ 级台阶的石梯。
由于陆陆的蹄子跨度限制，它每次向上迈步时只有两种选择：
1. 优雅地一步跨上 1 个台阶；
2. 或者是用力一蹦，一步跨过 2 个台阶。
陆陆必须刚好到达第 $n$ 个台阶，请你编写程序，计算小鹿陆陆上到第 $n$ 个台阶一共有几种不同的走法。
输入格式
一行，包含一个正整数 $n$ ($1 \lt n \lt 20$)，表示台阶的总数量。
输出格式
输出一行，一个整数，表示上到第 $n$ 级台阶的走法总数。
样例 1
输入 (Input)
4
输出 (Output)
5
- 数据范围：$1 \lt n \lt 20$。
- **样例说明**：
当 $n = 4$ 时，共有 5 种不同的走法：
1. $1 + 1 + 1 + 1$
2. $1 + 1 + 2$
3. $1 + 2 + 1$
4. $2 + 1 + 1$
5. $2 + 2$
- **递推提示**：
设到达第 $i$ 级台阶的走法为 $dp[i]$。因为小鹿只能从第 $i-1$ 级台阶跨 1 步到达，或者从第 $i-2$ 级台阶跨 2 步到达，所以有：
$$dp[i] = dp[i-1] + dp[i-2]$$
其中初始状态为 $dp[1] = 1$，$dp[2] = 2$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功