火影忍者：忍者护额排列任务

题目描述

木叶村正在进行一次忍者训练任务。

为了测试新生忍者的阵型安排能力，卡卡西老师设计了一个挑战：

有一排连续的 n 个训练位置。

每个位置可以放置一种忍者标记：

火之印记（红色）
水之印记（蓝色）

但是为了保证查克拉稳定：

两个火之印记不能出现在相邻的位置。

例如：

合法：

红 蓝 红 蓝

蓝 红 蓝 蓝

不合法：

红 红 蓝

因为两个红色印记连续出现，会导致查克拉冲突。

现在给定训练位置数量 n，请计算：

一共有多少种满足条件的排列方式。

---

输入格式

输入一个整数：

n

表示训练位置数量。

---

输出格式

输出一个整数：

表示满足要求的不同排列数量。

---

数据范围

1 ≤ n ≤ 50

---

样例输入1

1

样例输出1

2

---

样例解释

只有一个位置：

可以放：

红

或者：

蓝

所以：

答案为：

2

---

样例输入2

3

样例输出2

5

---

样例解释

三个位置所有合法方案：

蓝 蓝 蓝

蓝 蓝 红

蓝 红 蓝

红 蓝 蓝

红 蓝 红

共：

5种

测试点编号	n	难度层级	特殊性质	设计目的
1		弱数据	只访问 dp[1]	检查最小合法输入
2			只访问 dp[2]	检查第二个初始化值
3			第一次进入循环	检查递推起点
4			短递推	检查循环边界
5				检查连续递推
6	10	正常数据	小规模常规递推	覆盖多轮循环
7	20		中等规模递推	检查数组读写
8	30		中等偏大递推	检查答案增长
9	40		接近 int 上界	区分整型范围风险
10	45	极限数据	超过 int	卡 int 存储错误
11	50		大规模递推	检查 long long
12	54		数组安全上界附近	覆盖最大安全下标附近