>>368
ああなるほど。

std::map<int, int>m;
int fib(int n) {
std::map<int, int>::const_iteratorit = m.find(n);
return it != m.end() ? it->second : m.insert(std::pair<int, int>(n, fib(n-1) + fib(n-2))).first->second;
}

int main(int argc, char* argv[]) {
const int n = 40;
m.insert(std::pair<int, int>(0, 2));
m.insert(std::pair<int, int>(1, 3));
printf("%d\n", fib(n));
return 0;
}

としたら劇的に速くなりました。