class Solution { private: unordered_map<int,int> m; public: int Fibonacci(int n) { if(n == 1 || n == 2) { return 1; } int pre = 0; if(m.find(n - 1) == m.end()) { pre = Fibonacci(n - 1); m.insert({n - 1, pre}); } else { pre = m[n - 1]; } int prepre = 0; if(m.find(n - 2) == m.end()) { prepre = Fibonacci(n - 2); m.insert({n - 2, prepre}); } else { prepre = m[n - 2]; } return prepre + pre; } };