动态斐波那契程序C++

Question

不完全确定我是否正确实现了它，但我尝试对这个 fib 程序使用记忆化，结果发现它比我不使用记忆化要慢，有人知道为什么会发生这种情况吗？

~找到序列中的第 39 位数字。

*没有地图的结果（记忆）： 39 63245986 程序花费的时间是：1.000000 秒

*带有地图的结果： 39 63245986 程序花费的时间是：35.000000 秒

---

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int fibNum(int n) {

    map <int, int> mp = {};

    if(mp.find(n) != mp.end()){
        return mp[n];
    } else 
/* Remove this top part for non-map way*/

    if (n == 1 || n == 2){
        return 1;
    } else if (n == 0){
        return 0;
    } else {
        int answer = fibNum(n - 1) + fibNum(n - 2);
        mp[n] = answer; 
/* Remove this part about assigning value to the key*/
        return answer;
    }
    return 0;
}

/*Running the Fibonnac Programme, main programme is above*/

int main() {
    int term; cin >> term;
    
    time_t start,end;
    time(&start);
    ios_base::sync_with_stdio(false); 

    cout << fibNum(term) << endl;

    time(&end);

    double timeTaken = double(end - start);
    cout << "Time taken by program is : " << fixed 
        << timeTaken << ' ' << " sec\n"; 

    return 0;
}

Answer 1

在您的

fibNum

函数中，您需要通过在地图中查找 n 来

使用

地图，然后再诉诸递归调用

fibNum(n - 1)

和

fibNum(n - 2)

。

您还需要将映射作为参数传递给函数。