剑指Offer对答如流系列

面试题9：求斐波那契数列第n项

题目描述

写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：

在这里插入图片描述

解法讨论

直接写递归的话，是绝对OK的，但是你要明白一个道理，凡是递归能够完成的，递推也能够，而且性能还要优于递归，但是递推写起来总要难于递归。

对于斐波那契数列类型的习题，如果你要直接写递归函数(通常的那种递归，后面会有优化)，会出现比较多的重复计算，加之递归深度消耗的空间复杂度和时间复杂度代价是比较大的。

这里递推的写法可以解决斐波那契数列递归写法的弊端。

我们采用从下往上计算，把计算过了的值保存起来，下次参与计算直接使用：先由f(0)和f(1)计算f(2)，再由f(1)和f(2)计算f(3)……以此类推就行了，计算第n个时，只要保存第n-1和第n-2项就可以了。

递推解法：

    public class Fibonacci {
        public long Fib(long n) {
            if (n < 0)
                throw new RuntimeException("下标错误，应从0开始！");
            if (n == 0)
                return 0;
            if (n == 1)
                return 1;
            long prePre = 0;
            long pre = 1;
            long result = 1;
            for (long i = 2; i <= n; i++) {
                result = prePre + pre;
                prePre = pre;
                pre = result;
            }
            return result;
        }
    }

当然，如果你非常想用递归，但是又不想有那么高的时间复杂度，有没有办法？有，当然有。线性代数中有这方面的讨论。

斐波那契数列有以下公式
在这里插入图片描述

根据公式，如果你想求f(n)，只需要对矩阵求(n-1)次方即可，但此时时间复杂度仍为O(n)。利用递归的思路计算乘方，即可将时间复杂度降低为O(logn)。这里给出对乘方函数的递归代码

乘方的性质的性质如下

递归解答：

Matrix2By2 MatrixPower(unsigned int n)
{
    assert(n > 0);
 
    Matrix2By2 matrix;
    if(n == 1)
    {
        matrix = Matrix2By2(1, 1, 1, 0);
    }
    else if(n % 2 == 0)
    {
        matrix = MatrixPower(n / 2);
        matrix = MatrixMultiply(matrix, matrix);
    }
    else if(n % 2 == 1)
    {
        matrix = MatrixPower((n - 1) / 2);
        matrix = MatrixMultiply(matrix, matrix);
        matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
    }
 
    return matrix;
}

数学学得好，有用吗？这道题的解答能证明吧。

拓展

斐波那契数列的变形有很多。

比如剑指Offer后面的拓展：青蛙跳台阶问题和矩形覆盖问题，希望当你分析一些问题的时候，脑海里有斐波那契数列的数学模型。

（1）拓展题目1：青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

将跳法总数记为f(n)
f(1)=1
f(2)=2
当n>2时，第一次跳1级的话，还有f(n-1)种跳法；
当n>2时，第一次跳2级的话，还有f(n-2)种跳法

f(n)=f(n-1)+f(n-2)的递推式能够悟出来吧。

(2) 拓展题目2：矩形覆盖问题

用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？

当n = 1时，有一种方法。
当n = 2时，有两种方法。
当n >= 3时，和斐波那契数列类似。

第一步竖着放，有f(n-1)种方法；第一步横着放，有f(n-2)种方法。所以f(n)=f(n-1)+f(n-2)。

除了斐波那契数列简单直观的数学模型，我们也应该加强一下科学归纳法的思想。