#include <iostream>
#include <unordered_map>

std::unordered_map<int, int> memo {};

int fib(int n) {
    if (memo.count(n) == 1) {
        return memo[n];
    }

    int result {};
    if (n <= 2) {
        result = 1;
    } else {
        result = fib(n - 1) + fib(n - 2);
    }

    memo[n] = result;
    return result;
}

int main() {
    for (int i = 1; i < 10; i++) {
        std::cout << fib(i) << std::endl;
    }
    return 0;
}