#include <iostream>

#include <cstring>

using namespace std;

int cnt = 0;

int f1(int n) {

cnt++;

if (n<3) return 1;

return f1(n-1) + f1(n-2);

}

int a[100];

int f2(int n) {

cnt++;

if (n<3) return 1;

if (a[n]) return a[n];

return a[n] = f2(n-1) + f2(n-2);

}

int f3(const int n) {

int b[n+1];

memset(b, 0, sizeof(b));

b[1] = b[2] = 1;

for(int i=3; i<=n; i++) {

cnt++;

b[i] = b[i-1] + b[i-2];

}

return b[n];

}

int main() {

int n = 30;

cout << f1(n) << endl;

cout << "f1 cnt=" << cnt << endl;

cnt = 0;

cout << f2(n) << endl;

cout << "f2 cnt=" << cnt << endl;

cnt = 0;

cout << f3(n) << endl;

cout << "f3 cnt=" << cnt << endl;

return 0;

}