Fibonacci with dynamic programming not working!

[TheDovah7]

Hi!

I'm new to c++ and I'm trying to learn it by doing some recurison. However my fibonacci program (using dynamic programming) doesn't seem to work faster than with normal recursion. What am I doing wrong?

#include <iostream>
#include <unordered_map>

using namespace std;

int fib(int n, unordered_map<int,int> memo)
{
    if (memo.find(n) != memo.end()) return memo[n];
    if(n <= 2) return 1;
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

int main()
{
    cout << "What fibonacci number do you want?" << endl;
    int num;
    unordered_map<int,int> memoization;
    cin >> num;
    cout << fib(num, memoization) << endl;
    system("PAUSE");
}

[lastchance]

Pass your map by reference, not value. Otherwise it's a very expensive copy.
int fib(int n, unordered_map<int,int> &memo)

You've still got search overheads anyway (and in the case of a "find" you will actually end up searching twice). Use an array.

And it's always going to be quicker by straight induction.