#include <iostream>

using namespace std;

int recursive(int prev,int n) {
	if(n == 0) return 0;
	if(n == 1) {
		if (prev==0)
			return 2;
		if (prev==1)
			return 1;
	}
	if(prev==0)
		return recursive(0,n-1)+recursive(1,n-1);
	if(prev==1)
		return recursive(0,n-1);
}

int count_strings_recursive(int n) {
	return recursive(0,n);

}

int count_strings_dynamic(int n) {
	int a[n], b[n];
	a[0]=b[0]=1;
	for (int i = 1; i < n; i++) {
		a[i] = a[i-1] + b[i-1];
		b[i] = a[i-1];
	}
	return a[n-1] + b[n-1];
}

void menu() {
	cout << "Menu:\n";
	cout << "1) Recursive solution of task\n";
	cout << "2) Dynamic solution os task\n";
	cout << "0) Exit\n";
	cout << "~\n";
}

int main() {
	int n, op = -1;
	while (op != 0) {
		menu();
		cin >> op;
		cout << "Enter N:\n";
		cin >> n;
		if (op == 1) {
			cout << "Answer: " << count_strings_recursive(n) << "\n";
		} else if (op == 2) {
			cout << "Answer: " << count_strings_dynamic(n) << "\n";
		}
	}
}