I am watching this video. Basically it says that using a
dictionary
fibo1
fibo2
fibo1
#include <iostream>
#include <map>
int fibo1(int i, std::map<int,int>& m);
int fibo2(int i);
int main()
{
std::map<int,int> m;
m[1] = 1; m[2] = 1;
int n = 40;
std::cout << fibo1(n,m);
//std::cout << fibo2(n);
return 0;
}
int fibo1(int i, std::map<int,int>& m) {
if(m[i]==0) {
return fibo1(i-1,m)+fibo1(i-2,m);
}
return m[i];
}
int fibo2(int i) {
if(i==1 || i==2) {
return 1;
}
return fibo2(i-1)+fibo2(i-2);
}
You never actually write the fib[n]
at m[n]
, so you never look up anything and always recalculate it. Use m[i] = fibo1(i-1,m) + fibo1(i-2,m);
in the if statement rather than the return line.