#include <iostream>
#include <map>
using namespace std;
 
class DynamicProgramming
{
    public:
        int Fibonacci(int value) {
        	int &result = fibonacci_storage[value];
    		if (result) {
        		return result;
    		}
    		if (value <= 2 ){
        		return (result = 1);
    		}
    		return (result = Fibonacci(value - 1) + Fibonacci(value - 2));
        }
    private:
        std::map<int,int>fibonacci_storage;
};
 
 
int main() {
	DynamicProgramming dp;
	for (int i = 1 ; i != 20 ; i++) {
		cout << dp.Fibonacci(i) << endl;
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgRHluYW1pY1Byb2dyYW1taW5nCnsKICAgIHB1YmxpYzoKICAgICAgICBpbnQgRmlib25hY2NpKGludCB2YWx1ZSkgewogICAgICAgIAlpbnQgJnJlc3VsdCA9IGZpYm9uYWNjaV9zdG9yYWdlW3ZhbHVlXTsKICAgIAkJaWYgKHJlc3VsdCkgewogICAgICAgIAkJcmV0dXJuIHJlc3VsdDsKICAgIAkJfQogICAgCQlpZiAodmFsdWUgPD0gMiApewogICAgICAgIAkJcmV0dXJuIChyZXN1bHQgPSAxKTsKICAgIAkJfQogICAgCQlyZXR1cm4gKHJlc3VsdCA9IEZpYm9uYWNjaSh2YWx1ZSAtIDEpICsgRmlib25hY2NpKHZhbHVlIC0gMikpOwogICAgICAgIH0KICAgIHByaXZhdGU6CiAgICAgICAgc3RkOjptYXA8aW50LGludD5maWJvbmFjY2lfc3RvcmFnZTsKfTsKCgppbnQgbWFpbigpIHsKCUR5bmFtaWNQcm9ncmFtbWluZyBkcDsKCWZvciAoaW50IGkgPSAxIDsgaSAhPSAyMCA7IGkrKykgewoJCWNvdXQgPDwgZHAuRmlib25hY2NpKGkpIDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==