记忆化之后调用几次
给 fib 加上记忆化,再算一次 fib(12),数调用次数。
运行下面这段程序:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long fib_memo(int n, vector<long long>& memo, int& t) {
t++;
if (memo[n] != -1) return memo[n];
if (n < 2) return n;
memo[n] = fib_memo(n - 1, memo, t) + fib_memo(n - 2, memo, t);
return memo[n];
}
int main() {
vector<long long> memo(64, -1);
int t = 0;
fib_memo(12, memo, t);
cout << t << endl;
}
(本题用 g++ -std=c++17 -O0 编译。)
全部评论