LeetCode509.Fibonacci Number

leetcode 动态规划 DP 力扣简单

算法

发布日期: 2020-07-17

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

LeetCode509.Fibonacci Number

1、暴力递归

斐波那契数列的性质：

f1 = f2 = 1

fn = fn-1 - fn-2

从这个性质我们可以写出状态转移方程为：

很容易我们写出代码：

int fib(int N){
    if(N==0) return 0;
    if(N==1 || N==2) return 1;
    return fib(N-1) + fib(N-2);
}

这种写法很好想出，但算法时间复杂度非常高，指数级别，为O(2^N)。

原因是在递归的求解过程中有很多子问题被重复计算，这造成巨大的时间花费，使得算法变得十分低效。

2、带备忘录的记忆化递归

上一个解法提到提高解题效率的关键是如何消除子问题被重复计算。知道了这点，我们可以采用记备忘录的形式，每次求解子问题时，先不要着急计算，在备忘录中查询有无此子问题的答案，有的话直接返回结果；没有的话再递归求解子问题，同时将求解出的子问题答案记录在备忘录中。

这里使用一个vector数组当备忘录。

int calc(vector<int>& memo, int N){
    //如果memo[N]未计算过则计算，否则直接返回
    if(memo[N] == 0) 
        memo[N] = calc(memo,N-1) + calc(memo,N-2);
    return memo[N];
}

int fib(int N){
    if(N==0) return 0;
    if(N==1 || N==2) return 1;
    //memo 数组做备忘录
    vector<int> memo(N+1,0);
    //base case
    memo[1] = memo[2] = 1;
    return calc(memo,N);
}

有了memo备忘录存储每个子问题的计算结果，每次遇到相同子问题计算时直接查表即可。这样一来算法的时间复杂度大大降低了，为O(N)，算法的空间复杂度为O(N)。这在理论上已经达到了和动态规划的迭代解法一样的效率。

3、自底向上的迭代法

可以发现刚才的两种解法都是考虑自上而下的递归式解法，即我们从结果的最终态出发，向问题的基础状态靠近，从而求解出答案。实际上我们还可以从基础状态出发，通过迭代向上求解，这样的方法叫自底向上的迭代法。

int fib(int N){
    if(N==0) return 0;
    if(N==1 || N==2) return 1;
    //memo 数组做备忘录
    vector<int> memo(N+1,0);
    memo[1] = memo[2] = 1;
    for(int i = 3; i <= N; ++i){
        memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[N];
}

理论上，这种自底向上的迭代解法和自上而下的递归解法在时间复杂度方便是一样的，都是O(N)，但实际运行中，递归解法涉及较多的函数调用等耗费时间的操作，同样的问题规模可能要消耗稍微多一点时间。

一般来说，递归式的解法思路清晰，容易理解，迭代式的解法要求细节缜密，使用起来稍微复杂点，两者各有千秋。

4、优化

实际上，由斐波那契数的状态转移方程，我们可以发现每次求解的当前状态只与前两个状态有关系，即我们并不需要一整个备忘录表来存子问题的结果，只需要记住当前问题的前两个子问题结果。我们可以定义两个变量，每次利用这两个变量求出当前子问题的答案，再更新这两个变量，通过迭代获得问题的最终答案。

int fib(int N){
    if(N==0) return 0;
    if(N==1 || N==2) return 1;
    //f1,f2存储前两个状态，res记录结果
    int f1 = 1, f2 = 1, res = 0;
    for(int i = 3; i <= N; ++i){
        //根据前两个状态，计算当前状态值
        res = f1 + f2;
        //更新前两个状态
        f1 = f2;
        f2 = res;
    }
    return res;
}