本题与厦门大学机试题01字符串类似，也是考察到找数学规律

根据题意推理：

当n=1时 组合为0 1 共计2种

当n=2时 组合为00 10 01 共计3种

当n=3时 组合为000 100 010 001 101 共计5种

综上可以考虑此为斐波那契数列。

1 1 2 3 5 8 ……

简单验证如下：

当输入n=1 输出2 数列第3项

当输入n=2 输出3 数列第4项

当输入n=3 输出5 数列第5项

因此只需要构造出斐波那契数列，输出第n+2项目的结果即可

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int arr[N];

int main() {
	int n;
	cin >> n;
	arr[0] = 1, arr[1] = 1;
	for (int i = 2; i < n + 2; i++) {
		arr[i] = (arr[i - 1] + arr[i - 2]);
	}
	cout << arr[n + 1] << endl;

	return 0;
}