题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39

初始代码

class Solution {
public:
    int Fibonacci(int n) {

    }
};

解法1

斐波那契数列, 经典题. 它的递归定义式是f(n) = f(n-1) + f(n-2), 因此通过递归来实现.

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;

        return Fibonacci(n-1) + Fibonacci(n-2);
    }
};

上面的递归轨迹我们可以自己心里推导一下, 发现会有许多重复的计算. 比方说计算f(5)时根据f(5)=f(4)+f(3)计算了一遍f(3), 后续计算f(4)时又根据f(4)=f(3)+f(2)对f(3)重复计算了一次. 可以画个递归树便于形象地理解.

解法2

为了避免解法1中的重复计算, 我们可以给算法上面的递归算法加入记忆功能, 在发现有某个值是之前算过的时候, 就不再重复计算了.
通过一个数组来实现记忆. 由于题目提示n不超过39, 因此数组大小设置为40, 将数组所有元素初始化为不相干值-1, 以表示初始的每个值都是没计算过的.
为此另外写一个Fib函数来执行递归动作, Fibonacci函数作为顶层调用者, 它先初始化记忆数组, 然后再调用Fib函数执行递归计算.

class Solution {
public:
    int Fib(int dp[], int n)
    {
        if(n==0 || n==1) return n;
        if(dp[n] != -1) {
            return dp[n];
        }
        return dp[n] = Fib(dp, n-1) + Fib(dp, n-2);
    }
    int Fibonacci(int n) {
        int dp[40];
        for(int i=0; i<40; i++){
            dp[i] = -1;
        }
        return Fib(dp, n);
    }
};

解法3

考虑到递归对栈空间消耗较大, 题目本身n最大值也就39, 直接声明一个数组从数列的第0号和第1号元素依次往后递推, 保存每个值. 递推到数列的第n个数时直接返回, 这个方法空间复杂度也不大. 时间复杂度的话, 就是依次O(n)的遍历.

class Solution {
public:
    int Fibonacci(int n) {
        int arr[40];
        arr[0] = 0;
        arr[1] = 1;
        for(int i=2; i<=n; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n];
    }
};

解法4

上面的三种解法, 只有解法2是较能体现算法水平的, 解法1和3都是比较朴素的做法.
既然解法1存在形如解法2的更优解.
那能不能也为解法3找到一个优化点并得到更优解呢?
YES
解法3所蕴含的思想其实是自底向上的动态规划思想. 通过先着眼于解决局部的矛盾, 积少成多, 最终解决复杂问题. 这不同于递归在开始时就着眼于复杂问题, 通过逐级分解并在抵达递归出口后再回溯, 形成一个自顶向下&触底反弹的解题轨迹.

动态规划既然只关注局部矛盾, 那么对于斐波那契数列, 要求得第i个斐波那契数时的局部矛盾就是第i-1个和第i-2个是什么, 无需关注其它的. 因此, 解法3采用数组来保存整个计算过程算过的数是不必要的----仅需要两个变量, 一个保存第i-1个数, 一个保存第i-2个数, 我们就足以据此算出第i个数并推进算法向前一步了.

下面是实现的代码, 睿智而简洁:

代码中使用a来保存第i-2个数, b来保存第i-1个数. 每次更新a, b的方式也耍了一点小技巧, 没有借助额外的变量辅助计算.

class Solution {
public:
    int Fibonacci(int n) {
        int a=0, b=1;
        while(n-->0){
            b = a + b;
            a = b - a;
        }
        return a;
    }
};