2294. 御兽宗的灵兔繁衍计划
1000ms
256MB
简单
递推算法
题目描述
御兽宗的见习弟子小明最近领养了一对刚出生的“赛博灵兔”。根据《御兽秘籍》，这种灵兔具有神奇的繁衍规律：
1. 刚出生的小灵兔需要经过 1 个月的成长才能成为大灵兔。
2. 大灵兔再过 1 个月（即出生满 2 个月）就可以生育 1 对小灵兔，并且此后每个月都能生育 1 对小灵兔。
3. 在御兽宗聚灵阵的庇护下，所有的灵兔长生不死，不会发生死亡。
小明想知道，在第 $n$ 个月时，他一共能拥有多少对灵兔？（第 1 个月时，只有初始的那 1 对刚出生的小灵兔）。
输入格式
一行，包含一个正整数 $n$ ($1 \le n \le 40$)，表示经过的月份。
输出格式
输出一行，一个整数，表示第 $n$ 个月后灵兔的总对数。
样例 1
输入 (Input)
5
输出 (Output)
5
样例说明
- 对于所有数据：$1 \le n \le 40$。
- **样例解释**：
- 第 1 个月：1 对小灵兔（共 1 对）
- 第 2 个月：小灵兔长大，变为 1 对大灵兔（共 1 对）
- 第 3 个月：大灵兔生了 1 对小灵兔（共 2 对）
- 第 4 个月：大灵兔继续生 1 对小灵兔，上月生的小灵兔长大（共 3 对）
- 第 5 个月：共 5 对灵兔
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功