斐波那契递归与迭代方式

初学算法和数据结构，直接就用了一下的递归。结果很显然，超时了。

class Solution {
public:
    int fib(int n) {
        if(n==0)
        {
            return 0;
        }
        if(n==1)
        {
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }
};

由于递归进行了很多次重复的计算，

所以只需要创建一个散列表来存储每次计算的值，

当下一次遇到时，直接从散列表取出即可。

class Solution {
public:
    map<int, int>mp;
    int dfs(int n)
    {
        if (n == 0)
            return 0;
        else if (n == 1)
            return 1;
        else if (mp.count(n))
            return mp[n];
        mp[n - 1] = dfs(n - 1) % 1000000007;
        mp[n - 2] = dfs(n - 2) % 1000000007;
        mp[n] = (mp[n - 1] + mp[n - 2]) % 1000000007;
        return mp[n];
    }
    int fib(int n) {
        return dfs(n);
    }
};

还看到了另一种方法，简单的迭代。

创建一个数组来存放值。

class Solution {
public:
    int fib(int n) {
        vector<int> dp;
        for(int i=0;i<=n;i++)
        {
            if(i==0)
            {
                dp.push_back(0);
            }
            else if(i==1)
            {
                dp.push_back(1);
            }
            else
                dp.push_back((dp[i-1]+dp[i-2])%1000000007);
        }
        return dp[n];
    }
};