C memoization not appending map object-CodePudding

I am trying to practice basic dynamic programming in C , but for some reason, it isn't inserting new values into the std::map object. As a result, it just runs like a standard fibonacci function instead of the fast version made with dynamic programming. Can anyone tell me what I did wrong?

int fib(int n, std::map<int, int> memo = {}) {
    if (memo.count(n) >= 1) {
        return memo[n];
    }
    if (n <= 2) {
        return 1;
    }
    else {
        int result = fib(n - 1, memo)   fib(n - 2, memo);
        memo.insert(std::pair<int,int>(n,result));
        return result;
    }
}

CodePudding user response：

You're creating a new map each time, as you're passing memo by value, not by reference.

An alternative way to implement this is to create the map once, and then pass it by reference to the actual implementation. The example below does this, and has the advantage that it hides how you do the memoization:

int fib(int n)
{
    std::map<int, int> memo;
    return fib_impl(n, memo)
}

int fib_impl(int n, std::map<int, int> &memo) {
    if (memo.count(n) >= 1) {
        return memo[n];
    }
    if (n <= 2) {
        return 1;
    }
    else {
        int result = fib(n - 1, memo)   fib(n - 2, memo);
        memo.insert(std::pair<int,int>(n,result));
        return result;
    }
}

CodePudding user response：

Passing memo as value type making things slower. You can pass memo as reference type like below:

int fib(int n, std::map<int, int> &memo) {
    if (memo.count(n) >= 1) {
        return memo[n];
    }
    if (n <= 2) {
        return 1;
    }
    else {
        int result = fib(n - 1, memo)   fib(n - 2, memo);
        memo.insert(std::pair<int,int>(n,result));
        return result;
    }
}
int main(){
    map<int,int>memo;
    cout<<fib(5,memo)<<"\n";
}

Or, you can global declaration of memo.

map<int,int>memo; 
int fib(int n) {
    if(memo.count(n)>=1)return memo[n];
    if (n <= 2) {
        return 1;
    }
    else {
        int result = fib(n - 1)   fib(n - 2);
        memo.insert(std::pair<int,int>(n,result));
        return result;
    }
}

int main(){
     
     cout<<fib(10)<<"\n";
}