#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int dp[20];
int rec(int x) {
    if(x <= 2) {
        return 1;
    }

    if(dp[x] != -1) {
        return dp[x];
    }

    return dp[x] = rec(x - 1) + rec(x - 2);
}
int main()
{
    memset(dp, -1, sizeof dp);
    cout << rec(8) << endl;

    return 0;
}

// rec(5) = rec(4) +  rec(3)  = 3 + 2 = 5
// rec(4) = rec(3) + rec(2) = 2 + 1 = 3
// rec(3) = rec(2) + rec(1) = 1 + 1 = 2
// rec(2) = 1
// rec(1) = 1
// rec(2) = 2
// rec(3) = rec(2) + rec(1) = 1 + 1 = 2
// rec(2) = 1
// rec(1) = 1