C++ memoization not appending map object
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;
}
}
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;
}
}